Merging upstream version 1.72.1+dfsg1.

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

1 files changed, 182 insertions, 0 deletions

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)
+    }
+}