gix_negotiate/
lib.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//! 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, 'cache> = gix_revwalk::Graph<'find, 'cache, 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::get_or_insert_default::Error;