vendor/gix-negotiate-0.13.2/src/lib.rs - toolchain/rustc - Git at Google

 //! 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, Debug, 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_revwalk::Graph<'find, gix_revwalk::graph::Commit<Metadata>>;

 /// A map associating an object id with its commit-metadata.
 pub type IdMap = gix_revwalk::graph::IdMap<gix_revwalk::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: Option<usize>) -> usize {
     let current_size = match window_size {
         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_revwalk::graph::try_lookup_or_insert_default::Error;
	//! 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, Debug, 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_revwalk::Graph<'find, gix_revwalk::graph::Commit<Metadata>>;

	/// A map associating an object id with its commit-metadata.
	pub type IdMap = gix_revwalk::graph::IdMap<gix_revwalk::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: Option<usize>) -> usize {
	let current_size = match window_size {
	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_revwalk::graph::try_lookup_or_insert_default::Error;