gix_negotiate/lib.rs
1//! An implementation of negotiation algorithms to help the server figure out what we have in common so it can optimize
2//! the pack it sends to only contain what we don't have.
3#![deny(rust_2018_idioms, missing_docs)]
4#![forbid(unsafe_code)]
5mod consecutive;
6mod noop;
7mod skipping;
8
9bitflags::bitflags! {
10 /// Multi purpose, shared flags that are used by negotiation algorithms and by the caller as well
11 ///
12 /// However, in this crate we can't implement the calling side, so we marry this type to whatever is needed in downstream crates.
13 #[derive(Debug, Default, Copy, Clone)]
14 pub struct Flags: u8 {
15 /// The object is already available locally and doesn't need to be fetched by the remote.
16 const COMPLETE = 1 << 0;
17 /// A commit from an alternate object database.
18 const ALTERNATE = 1 << 1;
19
20 /// The revision is known to be in common with the remote.
21 ///
22 /// Used by `consecutive` and `skipping`.
23 const COMMON = 1 << 2;
24 /// The revision has entered the priority queue.
25 ///
26 /// Used by `consecutive` and `skipping`.
27 const SEEN = 1 << 3;
28 /// The revision was popped off our primary priority queue, used to avoid double-counting of `non_common_revs`
29 ///
30 /// Used by `consecutive` and `skipping`.
31 const POPPED = 1 << 4;
32
33 /// The revision is common and was set by merit of a remote tracking ref (e.g. `refs/heads/origin/main`).
34 ///
35 /// Used by `consecutive`.
36 const COMMON_REF = 1 << 5;
37
38 /// 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.
39 /// We won't tell the server about its ancestors.
40 ///
41 /// Used by `skipping`.
42 const ADVERTISED = 1 << 6;
43 }
44}
45
46/// Additional data to store with each commit when used by any of our algorithms.
47///
48/// It's shared among those who use the [`Negotiator`] trait, and all implementations of it.
49#[derive(Default, Debug, Copy, Clone)]
50pub struct Metadata {
51 /// Used by `skipping`.
52 /// Only used if commit is not COMMON
53 pub original_ttl: u16,
54 /// Used by `skipping`.
55 pub ttl: u16,
56 /// Additional information about each commit
57 pub flags: Flags,
58}
59
60/// The graph our callers use to store traversal information, for (re-)use in the negotiation implementation.
61pub type Graph<'find, 'cache> = gix_revwalk::Graph<'find, 'cache, gix_revwalk::graph::Commit<Metadata>>;
62
63/// A map associating an object id with its commit-metadata.
64pub type IdMap = gix_revwalk::graph::IdMap<gix_revwalk::graph::Commit<Metadata>>;
65
66/// The way the negotiation is performed.
67#[derive(Default, Debug, Copy, Clone, Eq, PartialEq)]
68pub enum Algorithm {
69 /// Do not send any information at all, which typically leads to complete packs to be sent.
70 Noop,
71 /// Walk over consecutive commits and check each one. This can be costly be assures packs are exactly the size they need to be.
72 #[default]
73 Consecutive,
74 /// Like `Consecutive`, but skips commits to converge faster, at the cost of receiving packs that are larger than they have to be.
75 Skipping,
76}
77
78impl std::fmt::Display for Algorithm {
79 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
80 match self {
81 Algorithm::Noop => "noop",
82 Algorithm::Consecutive => "consecutive",
83 Algorithm::Skipping => "skipping",
84 }
85 .fmt(f)
86 }
87}
88
89/// Calculate how many `HAVE` lines we may send in one round, with variation depending on whether the `transport_is_stateless` or not.
90/// `window_size` is the previous (or initial) value of the window size.
91pub fn window_size(transport_is_stateless: bool, window_size: Option<usize>) -> usize {
92 let current_size = match window_size {
93 None => return 16,
94 Some(cs) => cs,
95 };
96 const PIPESAFE_FLUSH: usize = 32;
97 const LARGE_FLUSH: usize = 16384;
98
99 if transport_is_stateless {
100 if current_size < LARGE_FLUSH {
101 current_size * 2
102 } else {
103 current_size * 11 / 10
104 }
105 } else if current_size < PIPESAFE_FLUSH {
106 current_size * 2
107 } else {
108 current_size + PIPESAFE_FLUSH
109 }
110}
111
112impl Algorithm {
113 /// Create an instance of a negotiator which implements this algorithm.
114 pub fn into_negotiator(self) -> Box<dyn Negotiator> {
115 match &self {
116 Algorithm::Noop => Box::new(noop::Noop) as Box<dyn Negotiator>,
117 Algorithm::Consecutive => Box::<consecutive::Algorithm>::default(),
118 Algorithm::Skipping => Box::<skipping::Algorithm>::default(),
119 }
120 }
121}
122
123/// A delegate to implement a negotiation algorithm.
124pub trait Negotiator {
125 /// Mark `id` as common between the remote and us.
126 ///
127 /// These ids are typically the local tips of remote tracking branches.
128 fn known_common(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_, '_>) -> Result<(), Error>;
129
130 /// Add `id` as starting point of a traversal across commits that aren't necessarily common between the remote and us.
131 ///
132 /// These tips are usually the commits of local references whose tips should lead to objects that we have in common with the remote.
133 fn add_tip(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_, '_>) -> Result<(), Error>;
134
135 /// 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.
136 ///
137 /// Returns `None` if we have exhausted all options, which might mean we have traversed the entire commit graph.
138 fn next_have(&mut self, graph: &mut Graph<'_, '_>) -> Option<Result<gix_hash::ObjectId, Error>>;
139
140 /// Mark `id` as being common with the remote (as informed by the remote itself) and return `true` if we knew it was common already.
141 ///
142 /// We can assume to have already seen `id` as we were the one to inform the remote in a prior `have`.
143 fn in_common_with_remote(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_, '_>) -> Result<bool, Error>;
144}
145
146/// An error that happened during any of the methods on a [`Negotiator`].
147pub type Error = gix_revwalk::graph::get_or_insert_default::Error;