Merging upstream version 1.72.1+dfsg1.

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

4 files changed, 516 insertions, 0 deletions

diff --git a/vendor/gix-negotiate/src/consecutive.rs b/vendor/gix-negotiate/src/consecutive.rs
new file mode 100644
index 000000000..f213cd949
--- /dev/null
+++ b/vendor/gix-negotiate/src/consecutive.rs
@@ -0,0 +1,167 @@
+use gix_hash::ObjectId;
+use gix_revision::graph::CommitterTimestamp;
+
+use crate::{Error, Flags, Negotiator};
+
+pub(crate) struct Algorithm {
+    revs: gix_revision::PriorityQueue<CommitterTimestamp, ObjectId>,
+    non_common_revs: usize,
+}
+
+impl Default for Algorithm {
+    fn default() -> Self {
+        Self {
+            revs: gix_revision::PriorityQueue::new(),
+            non_common_revs: 0,
+        }
+    }
+}
+
+impl Algorithm {
+    /// Add `id` to our priority queue and *add* `flags` to it.
+    fn add_to_queue(&mut self, id: ObjectId, mark: Flags, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        let mut is_common = false;
+        let mut has_mark = false;
+        if let Some(commit) = graph
+            .try_lookup_or_insert_commit(id, |data| {
+                has_mark = data.flags.intersects(mark);
+                data.flags |= mark;
+                is_common = data.flags.contains(Flags::COMMON);
+            })?
+            .filter(|_| !has_mark)
+        {
+            self.revs.insert(commit.commit_time, id);
+            if !is_common {
+                self.non_common_revs += 1;
+            }
+        }
+        Ok(())
+    }
+
+    fn mark_common(
+        &mut self,
+        id: ObjectId,
+        mode: Mark,
+        ancestors: Ancestors,
+        graph: &mut crate::Graph<'_>,
+    ) -> Result<(), Error> {
+        let mut is_common = false;
+        if let Some(commit) = graph
+            .try_lookup_or_insert_commit(id, |data| is_common = data.flags.contains(Flags::COMMON))?
+            .filter(|_| !is_common)
+        {
+            let mut queue = gix_revision::PriorityQueue::from_iter(Some((commit.commit_time, (id, 0_usize))));
+            if let Mark::ThisCommitAndAncestors = mode {
+                commit.data.flags |= Flags::COMMON;
+                if commit.data.flags.contains(Flags::SEEN) && !commit.data.flags.contains(Flags::POPPED) {
+                    self.non_common_revs -= 1;
+                }
+            }
+            while let Some((id, generation)) = queue.pop_value() {
+                if graph
+                    .get(&id)
+                    .map_or(true, |commit| !commit.data.flags.contains(Flags::SEEN))
+                {
+                    self.add_to_queue(id, Flags::SEEN, graph)?;
+                } else if matches!(ancestors, Ancestors::AllUnseen) || generation < 2 {
+                    if let Some(commit) = graph.try_lookup_or_insert_commit(id, |_| {})? {
+                        for parent_id in commit.parents.clone() {
+                            let mut prev_flags = Flags::default();
+                            if let Some(parent) = graph
+                                .try_lookup_or_insert_commit(parent_id, |data| {
+                                    prev_flags = data.flags;
+                                    data.flags |= Flags::COMMON;
+                                })?
+                                .filter(|_| !prev_flags.contains(Flags::COMMON))
+                            {
+                                if prev_flags.contains(Flags::SEEN) && !prev_flags.contains(Flags::POPPED) {
+                                    self.non_common_revs -= 1;
+                                }
+                                queue.insert(parent.commit_time, (parent_id, generation + 1))
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        Ok(())
+    }
+}
+
+impl Negotiator for Algorithm {
+    fn known_common(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        if graph
+            .get(&id)
+            .map_or(true, |commit| !commit.data.flags.contains(Flags::SEEN))
+        {
+            self.add_to_queue(id, Flags::COMMON_REF | Flags::SEEN, graph)?;
+            self.mark_common(id, Mark::AncestorsOnly, Ancestors::DirectUnseen, graph)?;
+        }
+        Ok(())
+    }
+
+    fn add_tip(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        self.add_to_queue(id, Flags::SEEN, graph)
+    }
+
+    fn next_have(&mut self, graph: &mut crate::Graph<'_>) -> Option<Result<ObjectId, Error>> {
+        loop {
+            let id = self.revs.pop_value().filter(|_| self.non_common_revs != 0)?;
+            let commit = graph.get_mut(&id).expect("it was added to the graph by now");
+            let flags = &mut commit.data.flags;
+            *flags |= Flags::POPPED;
+
+            if !flags.contains(Flags::COMMON) {
+                self.non_common_revs -= 1;
+            }
+
+            let (res, mark) = if flags.contains(Flags::COMMON) {
+                (None, Flags::COMMON | Flags::SEEN)
+            } else if flags.contains(Flags::COMMON_REF) {
+                (Some(id), Flags::COMMON | Flags::SEEN)
+            } else {
+                (Some(id), Flags::SEEN)
+            };
+
+            for parent_id in commit.parents.clone() {
+                if graph
+                    .get(&parent_id)
+                    .map_or(true, |commit| !commit.data.flags.contains(Flags::SEEN))
+                {
+                    if let Err(err) = self.add_to_queue(parent_id, mark, graph) {
+                        return Some(Err(err));
+                    }
+                }
+                if mark.contains(Flags::COMMON) {
+                    if let Err(err) = self.mark_common(parent_id, Mark::AncestorsOnly, Ancestors::AllUnseen, graph) {
+                        return Some(Err(err));
+                    }
+                }
+            }
+
+            if let Some(id) = res {
+                return Some(Ok(id));
+            }
+        }
+    }
+
+    fn in_common_with_remote(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<bool, Error> {
+        let known_to_be_common = graph
+            .get(&id)
+            .map_or(false, |commit| commit.data.flags.contains(Flags::COMMON));
+        self.mark_common(id, Mark::ThisCommitAndAncestors, Ancestors::DirectUnseen, graph)?;
+        Ok(known_to_be_common)
+    }
+}
+
+enum Mark {
+    AncestorsOnly,
+    ThisCommitAndAncestors,
+}
+
+enum Ancestors {
+    /// Traverse only the parents of a commit.
+    DirectUnseen,
+    /// Traverse all ancestors that weren't yet seen.
+    AllUnseen,
+}
diff --git a/vendor/gix-negotiate/src/lib.rs b/vendor/gix-negotiate/src/lib.rs
new file mode 100644
index 000000000..b05f944f8
--- /dev/null
+++ b/vendor/gix-negotiate/src/lib.rs
@@ -0,0 +1,144 @@
+//! An implementation of negotiation algorithms to help the server figure out what we have in common so it can optimize
+//! the pack it sends to only contain what we don't have.
+#![deny(rust_2018_idioms, missing_docs)]
+#![forbid(unsafe_code)]
+mod consecutive;
+mod noop;
+mod skipping;
+
+bitflags::bitflags! {
+    /// Multi purpose, shared flags that are used by negotiation algorithms and by the caller as well
+    ///
+    /// However, in this crate we can't implement the calling side, so we marry this type to whatever is needed in downstream crates.
+    #[derive(Debug, Default, Copy, Clone)]
+    pub struct Flags: u8 {
+        /// The object is already available locally and doesn't need to be fetched by the remote.
+        const COMPLETE = 1 << 0;
+        /// A commit from an alternate object database.
+        const ALTERNATE = 1 << 1;
+
+        /// The revision is known to be in common with the remote.
+        ///
+        /// Used by `consecutive` and `skipping`.
+        const COMMON = 1 << 2;
+        /// The revision has entered the priority queue.
+        ///
+        /// Used by `consecutive` and `skipping`.
+        const SEEN = 1 << 3;
+        /// The revision was popped off our primary priority queue, used to avoid double-counting of `non_common_revs`
+        ///
+        /// Used by `consecutive` and `skipping`.
+        const POPPED = 1 << 4;
+
+        /// The revision is common and was set by merit of a remote tracking ref (e.g. `refs/heads/origin/main`).
+        ///
+        /// Used by `consecutive`.
+        const COMMON_REF = 1 << 5;
+
+        /// The remote let us know it has the object. We still have to tell the server we have this object or one of its descendants.
+        /// We won't tell the server about its ancestors.
+        ///
+        /// Used by `skipping`.
+        const ADVERTISED = 1 << 6;
+    }
+}
+
+/// Additional data to store with each commit when used by any of our algorithms.
+///
+/// It's shared among those who use the [`Negotiator`] trait, and all implementations of it.
+#[derive(Default, Copy, Clone)]
+pub struct Metadata {
+    /// Used by `skipping`.
+    /// Only used if commit is not COMMON
+    pub original_ttl: u16,
+    /// Used by `skipping`.
+    pub ttl: u16,
+    /// Additional information about each commit
+    pub flags: Flags,
+}
+
+/// The graph our callers use to store traversal information, for (re-)use in the negotiation implementation.
+pub type Graph<'find> = gix_revision::Graph<'find, gix_revision::graph::Commit<Metadata>>;
+
+/// The way the negotiation is performed.
+#[derive(Default, Debug, Copy, Clone, Eq, PartialEq)]
+pub enum Algorithm {
+    /// Do not send any information at all, which typically leads to complete packs to be sent.
+    Noop,
+    /// Walk over consecutive commits and check each one. This can be costly be assures packs are exactly the size they need to be.
+    #[default]
+    Consecutive,
+    /// Like `Consecutive`, but skips commits to converge faster, at the cost of receiving packs that are larger than they have to be.
+    Skipping,
+}
+
+impl std::fmt::Display for Algorithm {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Algorithm::Noop => "noop",
+            Algorithm::Consecutive => "consecutive",
+            Algorithm::Skipping => "skipping",
+        }
+        .fmt(f)
+    }
+}
+
+/// Calculate how many `HAVE` lines we may send in one round, with variation depending on whether the `transport_is_stateless` or not.
+/// `window_size` is the previous (or initial) value of the window size.
+pub fn window_size(transport_is_stateless: bool, window_size: impl Into<Option<usize>>) -> usize {
+    let current_size = match window_size.into() {
+        None => return 16,
+        Some(cs) => cs,
+    };
+    const PIPESAFE_FLUSH: usize = 32;
+    const LARGE_FLUSH: usize = 16384;
+
+    if transport_is_stateless {
+        if current_size < LARGE_FLUSH {
+            current_size * 2
+        } else {
+            current_size * 11 / 10
+        }
+    } else if current_size < PIPESAFE_FLUSH {
+        current_size * 2
+    } else {
+        current_size + PIPESAFE_FLUSH
+    }
+}
+
+impl Algorithm {
+    /// Create an instance of a negotiator which implements this algorithm.
+    pub fn into_negotiator(self) -> Box<dyn Negotiator> {
+        match &self {
+            Algorithm::Noop => Box::new(noop::Noop) as Box<dyn Negotiator>,
+            Algorithm::Consecutive => Box::<consecutive::Algorithm>::default(),
+            Algorithm::Skipping => Box::<skipping::Algorithm>::default(),
+        }
+    }
+}
+
+/// A delegate to implement a negotiation algorithm.
+pub trait Negotiator {
+    /// Mark `id` as common between the remote and us.
+    ///
+    /// These ids are typically the local tips of remote tracking branches.
+    fn known_common(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_>) -> Result<(), Error>;
+
+    /// Add `id` as starting point of a traversal across commits that aren't necessarily common between the remote and us.
+    ///
+    /// These tips are usually the commits of local references whose tips should lead to objects that we have in common with the remote.
+    fn add_tip(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_>) -> Result<(), Error>;
+
+    /// Produce the next id of an object that we want the server to know we have. It's an object we don't know we have in common or not.
+    ///
+    /// Returns `None` if we have exhausted all options, which might mean we have traversed the entire commit graph.
+    fn next_have(&mut self, graph: &mut Graph<'_>) -> Option<Result<gix_hash::ObjectId, Error>>;
+
+    /// Mark `id` as being common with the remote (as informed by the remote itself) and return `true` if we knew it was common already.
+    ///
+    /// We can assume to have already seen `id` as we were the one to inform the remote in a prior `have`.
+    fn in_common_with_remote(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_>) -> Result<bool, Error>;
+}
+
+/// An error that happened during any of the methods on a [`Negotiator`].
+pub type Error = gix_revision::graph::lookup::commit::Error;
diff --git a/vendor/gix-negotiate/src/noop.rs b/vendor/gix-negotiate/src/noop.rs
new file mode 100644
index 000000000..5eabbb9e4
--- /dev/null
+++ b/vendor/gix-negotiate/src/noop.rs
@@ -0,0 +1,23 @@
+use gix_hash::ObjectId;
+
+use crate::{Error, Negotiator};
+
+pub(crate) struct Noop;
+
+impl Negotiator for Noop {
+    fn known_common(&mut self, _id: ObjectId, _graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        Ok(())
+    }
+
+    fn add_tip(&mut self, _id: ObjectId, _graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        Ok(())
+    }
+
+    fn next_have(&mut self, _graph: &mut crate::Graph<'_>) -> Option<Result<ObjectId, Error>> {
+        None
+    }
+
+    fn in_common_with_remote(&mut self, _id: ObjectId, _graph: &mut crate::Graph<'_>) -> Result<bool, Error> {
+        Ok(false)
+    }
+}
diff --git a/vendor/gix-negotiate/src/skipping.rs b/vendor/gix-negotiate/src/skipping.rs
new file mode 100644
index 000000000..06841b687
--- /dev/null
+++ b/vendor/gix-negotiate/src/skipping.rs
@@ -0,0 +1,182 @@
+use gix_hash::ObjectId;
+use gix_revision::graph::CommitterTimestamp;
+
+use crate::{Error, Flags, Metadata, Negotiator};
+
+pub(crate) struct Algorithm {
+    revs: gix_revision::PriorityQueue<CommitterTimestamp, ObjectId>,
+    non_common_revs: usize,
+}
+
+impl Default for Algorithm {
+    fn default() -> Self {
+        Self {
+            revs: gix_revision::PriorityQueue::new(),
+            non_common_revs: 0,
+        }
+    }
+}
+
+impl Algorithm {
+    /// Add `id` to our priority queue and *add* `flags` to it.
+    fn add_to_queue(&mut self, id: ObjectId, mark: Flags, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        let commit = graph.try_lookup_or_insert_commit(id, |entry| {
+            entry.flags |= mark | Flags::SEEN;
+        })?;
+        if let Some(timestamp) = commit.map(|c| c.commit_time) {
+            self.revs.insert(timestamp, id);
+            if !mark.contains(Flags::COMMON) {
+                self.non_common_revs += 1;
+            }
+        }
+        Ok(())
+    }
+
+    fn mark_common(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        let mut is_common = false;
+        if let Some(commit) = graph
+            .try_lookup_or_insert_commit(id, |entry| {
+                is_common = entry.flags.contains(Flags::COMMON);
+                entry.flags |= Flags::COMMON;
+            })?
+            .filter(|_| !is_common)
+        {
+            let mut queue = gix_revision::PriorityQueue::from_iter(Some((commit.commit_time, id)));
+            while let Some(id) = queue.pop_value() {
+                if let Some(commit) = graph.try_lookup_or_insert_commit(id, |entry| {
+                    if !entry.flags.contains(Flags::POPPED) {
+                        self.non_common_revs -= 1;
+                    }
+                })? {
+                    for parent_id in commit.parents.clone() {
+                        // This is a bit of a problem as there is no representation of the `parsed` based skip. However,
+                        // We assume that parents that aren't in the graph yet haven't been seen, and that's all we need.
+                        if !graph.contains(&parent_id) {
+                            continue;
+                        }
+                        let mut was_unseen_or_common = false;
+                        if let Some(parent) = graph
+                            .try_lookup_or_insert_commit(parent_id, |entry| {
+                                was_unseen_or_common =
+                                    !entry.flags.contains(Flags::SEEN) || entry.flags.contains(Flags::COMMON);
+                                entry.flags |= Flags::COMMON
+                            })?
+                            .filter(|_| !was_unseen_or_common)
+                        {
+                            queue.insert(parent.commit_time, parent_id);
+                        }
+                    }
+                }
+            }
+        }
+        Ok(())
+    }
+
+    fn push_parent(
+        &mut self,
+        entry: Metadata,
+        parent_id: ObjectId,
+        graph: &mut crate::Graph<'_>,
+    ) -> Result<bool, Error> {
+        let mut was_seen = false;
+        if let Some(parent) = graph
+            .get(&parent_id)
+            .map(|parent| {
+                was_seen = parent.data.flags.contains(Flags::SEEN);
+                parent
+            })
+            .filter(|_| was_seen)
+        {
+            if parent.data.flags.contains(Flags::POPPED) {
+                return Ok(false);
+            }
+        } else {
+            self.add_to_queue(parent_id, Flags::default(), graph)?;
+        }
+        if entry.flags.intersects(Flags::COMMON | Flags::ADVERTISED) {
+            self.mark_common(parent_id, graph)?;
+        } else {
+            let new_original_ttl = if entry.ttl > 0 {
+                entry.original_ttl
+            } else {
+                entry.original_ttl * 3 / 2 + 1
+            };
+            let new_ttl = if entry.ttl > 0 { entry.ttl - 1 } else { new_original_ttl };
+            let parent = graph.get_mut(&parent_id).expect("present or inserted");
+            if parent.data.original_ttl < new_original_ttl {
+                parent.data.original_ttl = new_original_ttl;
+                parent.data.ttl = new_ttl;
+            }
+        }
+        Ok(true)
+    }
+}
+
+impl Negotiator for Algorithm {
+    fn known_common(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        if graph
+            .get(&id)
+            .map_or(false, |commit| commit.data.flags.contains(Flags::SEEN))
+        {
+            return Ok(());
+        }
+        self.add_to_queue(id, Flags::ADVERTISED, graph)
+    }
+
+    fn add_tip(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> {
+        if graph
+            .get(&id)
+            .map_or(false, |commit| commit.data.flags.contains(Flags::SEEN))
+        {
+            return Ok(());
+        }
+        self.add_to_queue(id, Flags::default(), graph)
+    }
+
+    fn next_have(&mut self, graph: &mut crate::Graph<'_>) -> Option<Result<ObjectId, Error>> {
+        loop {
+            let id = self.revs.pop_value().filter(|_| self.non_common_revs != 0)?;
+            let commit = graph.get_mut(&id).expect("it was added to the graph by now");
+            commit.data.flags |= Flags::POPPED;
+
+            if !commit.data.flags.contains(Flags::COMMON) {
+                self.non_common_revs -= 1;
+            }
+            let mut to_send = None;
+            if !commit.data.flags.contains(Flags::COMMON) && commit.data.ttl == 0 {
+                to_send = Some(id);
+            }
+
+            let data = commit.data;
+            let mut parent_pushed = false;
+            for parent_id in commit.parents.clone() {
+                parent_pushed |= match self.push_parent(data, parent_id, graph) {
+                    Ok(r) => r,
+                    Err(err) => return Some(Err(err)),
+                }
+            }
+
+            if !data.flags.contains(Flags::COMMON) && !parent_pushed {
+                to_send = Some(id);
+            }
+
+            if let Some(to_send) = to_send {
+                return Some(Ok(to_send));
+            }
+        }
+    }
+
+    fn in_common_with_remote(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<bool, Error> {
+        let mut was_seen = false;
+        let known_to_be_common = graph.get(&id).map_or(false, |commit| {
+            was_seen = commit.data.flags.contains(Flags::SEEN);
+            commit.data.flags.contains(Flags::COMMON)
+        });
+        assert!(
+            was_seen,
+            "Cannot receive ACK for commit we didn't send a HAVE for: {id}"
+        );
+        self.mark_common(id, graph)?;
+        Ok(known_to_be_common)
+    }
+}