diff options
Diffstat (limited to 'vendor/gix-negotiate/src/lib.rs')
| -rw-r--r-- | vendor/gix-negotiate/src/lib.rs | 144 |
1 files changed, 144 insertions, 0 deletions
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; |