]>
Commit | Line | Data |
---|---|---|
fe692bf9 | 1 | use std::borrow::Cow; |
49aad941 | 2 | |
781aab86 | 3 | use gix_date::SecondsSinceUnixEpoch; |
fe692bf9 FG |
4 | use gix_negotiate::Flags; |
5 | use gix_odb::HeaderExt; | |
6 | use gix_pack::Find; | |
7 | ||
8 | use crate::remote::{fetch, fetch::Shallow}; | |
9 | ||
781aab86 | 10 | type Queue = gix_revwalk::PriorityQueue<SecondsSinceUnixEpoch, gix_hash::ObjectId>; |
0a29b90c FG |
11 | |
12 | /// The error returned during negotiation. | |
13 | #[derive(Debug, thiserror::Error)] | |
14 | #[allow(missing_docs)] | |
15 | pub enum Error { | |
16 | #[error("We were unable to figure out what objects the server should send after {rounds} round(s)")] | |
17 | NegotiationFailed { rounds: usize }, | |
fe692bf9 | 18 | #[error(transparent)] |
4b012472 | 19 | LookupCommitInGraph(#[from] gix_revwalk::graph::try_lookup_or_insert_default::Error), |
fe692bf9 FG |
20 | #[error(transparent)] |
21 | InitRefsIterator(#[from] crate::reference::iter::init::Error), | |
22 | #[error(transparent)] | |
23 | InitRefsIteratorPlatform(#[from] crate::reference::iter::Error), | |
24 | #[error(transparent)] | |
25 | ObtainRefDuringIteration(#[from] Box<dyn std::error::Error + Send + Sync + 'static>), | |
26 | #[error(transparent)] | |
27 | LoadIndex(#[from] gix_odb::store::load_index::Error), | |
0a29b90c FG |
28 | } |
29 | ||
fe692bf9 FG |
30 | #[must_use] |
31 | pub(crate) enum Action { | |
32 | /// None of the remote refs moved compared to our last recorded state (via tracking refs), so there is nothing to do at all, | |
33 | /// not even a ref update. | |
34 | NoChange, | |
35 | /// Don't negotiate, don't fetch the pack, skip right to updating the references. | |
36 | /// | |
37 | /// This happens if we already have all local objects even though the server seems to have changed. | |
38 | SkipToRefUpdate, | |
39 | /// We can't know for sure if fetching *is not* needed, so we go ahead and negotiate. | |
40 | MustNegotiate { | |
41 | /// Each `ref_map.mapping` has a slot here which is `true` if we have the object the remote ref points to locally. | |
42 | remote_ref_target_known: Vec<bool>, | |
43 | }, | |
44 | } | |
45 | ||
46 | /// This function is modeled after the similarly named one in the git codebase to do the following: | |
47 | /// | |
48 | /// * figure out all advertised refs on the remote *that we already have* and keep track of the oldest one as cutoff date. | |
49 | /// * mark all of our own refs as tips for a traversal. | |
50 | /// * mark all their parents, recursively, up to (and including) the cutoff date up to which we have seen the servers commit that we have. | |
51 | /// * pass all known-to-be-common-with-remote commits to the negotiator as common commits. | |
52 | /// | |
53 | /// This is done so that we already find the most recent common commits, even if we are ahead, which is *potentially* better than | |
54 | /// what we would get if we would rely on tracking refs alone, particularly if one wouldn't trust the tracking refs for some reason. | |
55 | /// | |
56 | /// Note that git doesn't trust its own tracking refs as the server *might* have changed completely, for instance by force-pushing, so | |
57 | /// marking our local tracking refs as known is something that's actually not proven to be correct so it's not done. | |
58 | /// | |
59 | /// Additionally, it does what's done in `transport.c` and we check if a fetch is actually needed as at least one advertised ref changed. | |
60 | /// | |
61 | /// Finally, we also mark tips in the `negotiator` in one go to avoid traversing all refs twice, since we naturally encounter all tips during | |
62 | /// our own walk. | |
63 | /// | |
64 | /// Return whether or not we should negotiate, along with a queue for later use. | |
65 | pub(crate) fn mark_complete_and_common_ref( | |
0a29b90c | 66 | repo: &crate::Repository, |
fe692bf9 FG |
67 | negotiator: &mut dyn gix_negotiate::Negotiator, |
68 | graph: &mut gix_negotiate::Graph<'_>, | |
69 | ref_map: &fetch::RefMap, | |
70 | shallow: &fetch::Shallow, | |
781aab86 | 71 | mapping_is_ignored: impl Fn(&fetch::Mapping) -> bool, |
fe692bf9 | 72 | ) -> Result<Action, Error> { |
781aab86 | 73 | let _span = gix_trace::detail!("mark_complete_and_common_ref", mappings = ref_map.mappings.len()); |
fe692bf9 | 74 | if let fetch::Shallow::Deepen(0) = shallow { |
49aad941 FG |
75 | // Avoid deepening (relative) with zero as it seems to upset the server. Git also doesn't actually |
76 | // perform the negotiation for some reason (couldn't find it in code). | |
fe692bf9 FG |
77 | return Ok(Action::NoChange); |
78 | } | |
79 | if let Some(fetch::Mapping { | |
80 | remote: fetch::Source::Ref(gix_protocol::handshake::Ref::Unborn { .. }), | |
81 | .. | |
82 | }) = ref_map.mappings.last().filter(|_| ref_map.mappings.len() == 1) | |
83 | { | |
84 | // There is only an unborn branch, as the remote has an empty repository. This means there is nothing to do except for | |
85 | // possibly reproducing the unborn branch locally. | |
86 | return Ok(Action::SkipToRefUpdate); | |
49aad941 FG |
87 | } |
88 | ||
fe692bf9 FG |
89 | // Compute the cut-off date by checking which of the refs advertised (and matched in refspecs) by the remote we have, |
90 | // and keep the oldest one. | |
781aab86 | 91 | let mut cutoff_date = None::<SecondsSinceUnixEpoch>; |
fe692bf9 FG |
92 | let mut num_mappings_with_change = 0; |
93 | let mut remote_ref_target_known: Vec<bool> = std::iter::repeat(false).take(ref_map.mappings.len()).collect(); | |
781aab86 | 94 | let mut remote_ref_included: Vec<bool> = std::iter::repeat(false).take(ref_map.mappings.len()).collect(); |
fe692bf9 FG |
95 | |
96 | for (mapping_idx, mapping) in ref_map.mappings.iter().enumerate() { | |
97 | let want_id = mapping.remote.as_id(); | |
98 | let have_id = mapping.local.as_ref().and_then(|name| { | |
99 | // this is the only time git uses the peer-id. | |
100 | let r = repo.find_reference(name).ok()?; | |
101 | r.target().try_id().map(ToOwned::to_owned) | |
102 | }); | |
103 | ||
781aab86 FG |
104 | // Even for ignored mappings we want to know if the `want` is already present locally, so skip nothing else. |
105 | if !mapping_is_ignored(mapping) { | |
106 | remote_ref_included[mapping_idx] = true; | |
107 | // Like git, we don't let known unchanged mappings participate in the tree traversal | |
108 | if want_id.zip(have_id).map_or(true, |(want, have)| want != have) { | |
109 | num_mappings_with_change += 1; | |
110 | } | |
fe692bf9 FG |
111 | } |
112 | ||
113 | if let Some(commit) = want_id | |
114 | .and_then(|id| graph.try_lookup_or_insert_commit(id.into(), |_| {}).transpose()) | |
115 | .transpose()? | |
116 | { | |
117 | remote_ref_target_known[mapping_idx] = true; | |
118 | cutoff_date = cutoff_date.unwrap_or_default().max(commit.commit_time).into(); | |
119 | } else if want_id.map_or(false, |maybe_annotated_tag| repo.objects.contains(maybe_annotated_tag)) { | |
120 | remote_ref_target_known[mapping_idx] = true; | |
121 | } | |
122 | } | |
123 | ||
fe692bf9 FG |
124 | if matches!(shallow, Shallow::NoChange) { |
125 | if num_mappings_with_change == 0 { | |
126 | return Ok(Action::NoChange); | |
781aab86 FG |
127 | } else if remote_ref_target_known |
128 | .iter() | |
129 | .zip(remote_ref_included) | |
130 | .filter_map(|(known, included)| included.then_some(known)) | |
131 | .all(|known| *known) | |
132 | { | |
fe692bf9 FG |
133 | return Ok(Action::SkipToRefUpdate); |
134 | } | |
135 | } | |
136 | ||
137 | // color our commits as complete as identified by references, unconditionally | |
138 | // (`git` is conditional here based on `deepen`, but it doesn't make sense and it's hard to extract from history when that happened). | |
139 | let mut queue = Queue::new(); | |
140 | mark_all_refs_in_repo(repo, graph, &mut queue, Flags::COMPLETE)?; | |
141 | mark_alternate_complete(repo, graph, &mut queue)?; | |
142 | // Keep track of the tips, which happen to be on our queue right, before we traverse the graph with cutoff. | |
143 | let tips = if let Some(cutoff) = cutoff_date { | |
144 | let tips = Cow::Owned(queue.clone()); | |
145 | // color all their parents up to the cutoff date, the oldest commit we know the server has. | |
146 | mark_recent_complete_commits(&mut queue, graph, cutoff)?; | |
147 | tips | |
148 | } else { | |
149 | Cow::Borrowed(&queue) | |
150 | }; | |
151 | ||
781aab86 FG |
152 | gix_trace::detail!("mark known_common").into_scope(|| -> Result<_, Error> { |
153 | // mark all complete advertised refs as common refs. | |
154 | for mapping in ref_map | |
155 | .mappings | |
156 | .iter() | |
157 | .zip(remote_ref_target_known.iter().copied()) | |
158 | // We need this filter as the graph wouldn't contain annotated tags. | |
159 | .filter_map(|(mapping, known)| (!known).then_some(mapping)) | |
fe692bf9 | 160 | { |
781aab86 FG |
161 | let want_id = mapping.remote.as_id(); |
162 | if let Some(common_id) = want_id | |
163 | .and_then(|id| graph.get(id).map(|c| (c, id))) | |
164 | .filter(|(c, _)| c.data.flags.contains(Flags::COMPLETE)) | |
165 | .map(|(_, id)| id) | |
166 | { | |
167 | negotiator.known_common(common_id.into(), graph)?; | |
168 | } | |
fe692bf9 | 169 | } |
781aab86 FG |
170 | Ok(()) |
171 | })?; | |
fe692bf9 FG |
172 | |
173 | // As negotiators currently may rely on getting `known_common` calls first and tips after, we adhere to that which is the only | |
174 | // reason we cached the set of tips. | |
781aab86 FG |
175 | gix_trace::detail!("mark tips", num_tips = tips.len()).into_scope(|| -> Result<_, Error> { |
176 | for tip in tips.iter_unordered() { | |
177 | negotiator.add_tip(*tip, graph)?; | |
178 | } | |
179 | Ok(()) | |
180 | })?; | |
fe692bf9 FG |
181 | |
182 | Ok(Action::MustNegotiate { | |
183 | remote_ref_target_known, | |
184 | }) | |
185 | } | |
186 | ||
781aab86 FG |
187 | /// Create a predicate that checks if a refspec mapping should be ignored. |
188 | /// | |
189 | /// We want to ignore mappings during negotiation if they would be handled implicitly by the server, which is the case | |
190 | /// when tags would be sent implicitly due to `Tags::Included`. | |
191 | pub(crate) fn make_refmapping_ignore_predicate( | |
fe692bf9 | 192 | fetch_tags: fetch::Tags, |
781aab86 FG |
193 | ref_map: &fetch::RefMap, |
194 | ) -> impl Fn(&fetch::Mapping) -> bool + '_ { | |
fe692bf9 FG |
195 | // With included tags, we have to keep mappings of tags to handle them later when updating refs, but we don't want to |
196 | // explicitly `want` them as the server will determine by itself which tags are pointing to a commit it wants to send. | |
197 | // If we would not exclude implicit tag mappings like this, we would get too much of the graph. | |
198 | let tag_refspec_to_ignore = matches!(fetch_tags, crate::remote::fetch::Tags::Included) | |
199 | .then(|| fetch_tags.to_refspec()) | |
200 | .flatten(); | |
781aab86 FG |
201 | move |mapping| { |
202 | tag_refspec_to_ignore.map_or(false, |tag_spec| { | |
203 | mapping | |
204 | .spec_index | |
205 | .implicit_index() | |
206 | .and_then(|idx| ref_map.extra_refspecs.get(idx)) | |
207 | .map_or(false, |spec| spec.to_ref() == tag_spec) | |
208 | }) | |
209 | } | |
210 | } | |
fe692bf9 | 211 | |
781aab86 FG |
212 | /// Add all `wants` to `arguments`, which is the unpeeled direct target that the advertised remote ref points to. |
213 | pub(crate) fn add_wants( | |
214 | repo: &crate::Repository, | |
215 | arguments: &mut gix_protocol::fetch::Arguments, | |
216 | ref_map: &fetch::RefMap, | |
217 | mapping_known: &[bool], | |
218 | shallow: &fetch::Shallow, | |
219 | mapping_is_ignored: impl Fn(&fetch::Mapping) -> bool, | |
220 | ) { | |
fe692bf9 FG |
221 | // When using shallow, we can't exclude `wants` as the remote won't send anything then. Thus we have to resend everything |
222 | // we have as want instead to get exactly the same graph, but possibly deepened. | |
223 | let is_shallow = !matches!(shallow, fetch::Shallow::NoChange); | |
224 | let wants = ref_map | |
225 | .mappings | |
226 | .iter() | |
227 | .zip(mapping_known) | |
781aab86 FG |
228 | .filter_map(|(m, known)| (is_shallow || !*known).then_some(m)) |
229 | .filter(|m| !mapping_is_ignored(m)); | |
fe692bf9 | 230 | for want in wants { |
fe692bf9 FG |
231 | let id_on_remote = want.remote.as_id(); |
232 | if !arguments.can_use_ref_in_want() || matches!(want.remote, fetch::Source::ObjectId(_)) { | |
233 | if let Some(id) = id_on_remote { | |
234 | arguments.want(id); | |
0a29b90c | 235 | } |
fe692bf9 FG |
236 | } else { |
237 | arguments.want_ref( | |
238 | want.remote | |
239 | .as_name() | |
240 | .expect("name available if this isn't an object id"), | |
241 | ) | |
242 | } | |
243 | let id_is_annotated_tag_we_have = id_on_remote | |
244 | .and_then(|id| repo.objects.header(id).ok().map(|h| (id, h))) | |
245 | .filter(|(_, h)| h.kind() == gix_object::Kind::Tag) | |
246 | .map(|(id, _)| id); | |
247 | if let Some(tag_on_remote) = id_is_annotated_tag_we_have { | |
248 | // Annotated tags are not handled at all by negotiators in the commit-graph - they only see commits and thus won't | |
249 | // ever add `have`s for tags. To correct for that, we add these haves here to avoid getting them sent again. | |
250 | arguments.have(tag_on_remote) | |
251 | } | |
252 | } | |
253 | } | |
0a29b90c | 254 | |
fe692bf9 FG |
255 | /// Remove all commits that are more recent than the cut-off, which is the commit time of the oldest common commit we have with the server. |
256 | fn mark_recent_complete_commits( | |
257 | queue: &mut Queue, | |
258 | graph: &mut gix_negotiate::Graph<'_>, | |
781aab86 | 259 | cutoff: SecondsSinceUnixEpoch, |
fe692bf9 | 260 | ) -> Result<(), Error> { |
781aab86 | 261 | let _span = gix_trace::detail!("mark_recent_complete", queue_len = queue.len()); |
fe692bf9 FG |
262 | while let Some(id) = queue |
263 | .peek() | |
264 | .and_then(|(commit_time, id)| (commit_time >= &cutoff).then_some(*id)) | |
265 | { | |
781aab86 | 266 | queue.pop_value(); |
fe692bf9 FG |
267 | let commit = graph.get(&id).expect("definitely set when adding tips or parents"); |
268 | for parent_id in commit.parents.clone() { | |
269 | let mut was_complete = false; | |
270 | if let Some(parent) = graph | |
271 | .try_lookup_or_insert_commit(parent_id, |md| { | |
272 | was_complete = md.flags.contains(Flags::COMPLETE); | |
273 | md.flags |= Flags::COMPLETE | |
274 | })? | |
275 | .filter(|_| !was_complete) | |
276 | { | |
277 | queue.insert(parent.commit_time, parent_id) | |
278 | } | |
279 | } | |
280 | } | |
281 | Ok(()) | |
282 | } | |
283 | ||
284 | fn mark_all_refs_in_repo( | |
285 | repo: &crate::Repository, | |
286 | graph: &mut gix_negotiate::Graph<'_>, | |
287 | queue: &mut Queue, | |
288 | mark: Flags, | |
289 | ) -> Result<(), Error> { | |
781aab86 | 290 | let _span = gix_trace::detail!("mark_all_refs"); |
fe692bf9 FG |
291 | for local_ref in repo.references()?.all()?.peeled() { |
292 | let local_ref = local_ref?; | |
293 | let id = local_ref.id().detach(); | |
294 | let mut is_complete = false; | |
295 | if let Some(commit) = graph | |
296 | .try_lookup_or_insert_commit(id, |md| { | |
297 | is_complete = md.flags.contains(Flags::COMPLETE); | |
298 | md.flags |= mark | |
299 | })? | |
300 | .filter(|_| !is_complete) | |
301 | { | |
302 | queue.insert(commit.commit_time, id); | |
303 | }; | |
304 | } | |
305 | Ok(()) | |
306 | } | |
307 | ||
308 | fn mark_alternate_complete( | |
309 | repo: &crate::Repository, | |
310 | graph: &mut gix_negotiate::Graph<'_>, | |
311 | queue: &mut Queue, | |
312 | ) -> Result<(), Error> { | |
781aab86 FG |
313 | let alternates = repo.objects.store_ref().alternate_db_paths()?; |
314 | let _span = gix_trace::detail!("mark_alternate_refs", num_odb = alternates.len()); | |
315 | ||
316 | for alternate_repo in alternates.into_iter().filter_map(|path| { | |
317 | path.ancestors() | |
318 | .nth(1) | |
319 | .and_then(|git_dir| crate::open_opts(git_dir, repo.options.clone()).ok()) | |
320 | }) { | |
fe692bf9 FG |
321 | mark_all_refs_in_repo(&alternate_repo, graph, queue, Flags::ALTERNATE | Flags::COMPLETE)?; |
322 | } | |
323 | Ok(()) | |
324 | } | |
325 | ||
326 | /// Negotiate the nth `round` with `negotiator` sending `haves_to_send` after possibly making the known common commits | |
327 | /// as sent by the remote known to `negotiator` using `previous_response` if this isn't the first round. | |
328 | /// All `haves` are added to `arguments` accordingly. | |
329 | /// Returns the amount of haves actually sent. | |
330 | pub(crate) fn one_round( | |
331 | negotiator: &mut dyn gix_negotiate::Negotiator, | |
332 | graph: &mut gix_negotiate::Graph<'_>, | |
333 | haves_to_send: usize, | |
334 | arguments: &mut gix_protocol::fetch::Arguments, | |
335 | previous_response: Option<&gix_protocol::fetch::Response>, | |
336 | mut common: Option<&mut Vec<gix_hash::ObjectId>>, | |
337 | ) -> Result<(usize, bool), Error> { | |
338 | let mut seen_ack = false; | |
339 | if let Some(response) = previous_response { | |
340 | use gix_protocol::fetch::response::Acknowledgement; | |
341 | for ack in response.acknowledgements() { | |
342 | match ack { | |
343 | Acknowledgement::Common(id) => { | |
344 | seen_ack = true; | |
345 | negotiator.in_common_with_remote(*id, graph)?; | |
346 | if let Some(ref mut common) = common { | |
347 | common.push(*id); | |
0a29b90c FG |
348 | } |
349 | } | |
fe692bf9 FG |
350 | Acknowledgement::Ready => { |
351 | // NOTE: In git, there is some logic dealing with whether to expect a DELIM or FLUSH package, | |
352 | // but we handle this with peeking. | |
353 | } | |
354 | Acknowledgement::Nak => {} | |
0a29b90c | 355 | } |
0a29b90c FG |
356 | } |
357 | } | |
fe692bf9 FG |
358 | |
359 | // `common` is set only if this is a stateless transport, and we repeat previously confirmed common commits as HAVE, because | |
360 | // we are not going to repeat them otherwise. | |
361 | if let Some(common) = common { | |
362 | for have_id in common { | |
363 | arguments.have(have_id); | |
364 | } | |
365 | } | |
366 | ||
367 | let mut haves_sent = 0; | |
368 | for have_id in (0..haves_to_send).map_while(|_| negotiator.next_have(graph)) { | |
369 | arguments.have(have_id?); | |
370 | haves_sent += 1; | |
371 | } | |
372 | // Note that we are differing from the git implementation, which does an extra-round of with no new haves sent at all. | |
373 | // For us it seems better to just say we are done when we know we are done, as potentially additional acks won't affect the | |
374 | // queue of any of our implementation at all (so the negotiator won't come up with more haves next time either). | |
375 | Ok((haves_sent, seen_ack)) | |
0a29b90c | 376 | } |