ilyagr.bsky.social
just playing with tangled
1// Copyright 2021 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![allow(missing_docs)]
16
17use std::fmt;
18use std::fmt::Display;
19
20use itertools::EitherOrBoth;
21
22use crate::backend::CommitId;
23use crate::index::Index;
24use crate::merge::trivial_merge;
25use crate::merge::Merge;
26use crate::op_store::RefTarget;
27use crate::op_store::RemoteRef;
28use crate::revset;
29
30/// Compares `refs1` and `refs2` targets, yields entry if they differ.
31///
32/// `refs1` and `refs2` must be sorted by `K`.
33pub fn diff_named_ref_targets<'a, 'b, K: Ord>(
34 refs1: impl IntoIterator<Item = (K, &'a RefTarget)>,
35 refs2: impl IntoIterator<Item = (K, &'b RefTarget)>,
36) -> impl Iterator<Item = (K, (&'a RefTarget, &'b RefTarget))> {
37 iter_named_pairs(
38 refs1,
39 refs2,
40 || RefTarget::absent_ref(),
41 || RefTarget::absent_ref(),
42 )
43 .filter(|(_, (target1, target2))| target1 != target2)
44}
45
46/// Compares remote `refs1` and `refs2` pairs, yields entry if they differ.
47///
48/// `refs1` and `refs2` must be sorted by `K`.
49pub fn diff_named_remote_refs<'a, 'b, K: Ord>(
50 refs1: impl IntoIterator<Item = (K, &'a RemoteRef)>,
51 refs2: impl IntoIterator<Item = (K, &'b RemoteRef)>,
52) -> impl Iterator<Item = (K, (&'a RemoteRef, &'b RemoteRef))> {
53 iter_named_pairs(
54 refs1,
55 refs2,
56 || RemoteRef::absent_ref(),
57 || RemoteRef::absent_ref(),
58 )
59 .filter(|(_, (ref1, ref2))| ref1 != ref2)
60}
61
62/// Iterates local `refs1` and remote `refs2` pairs by name.
63///
64/// `refs1` and `refs2` must be sorted by `K`.
65pub fn iter_named_local_remote_refs<'a, 'b, K: Ord>(
66 refs1: impl IntoIterator<Item = (K, &'a RefTarget)>,
67 refs2: impl IntoIterator<Item = (K, &'b RemoteRef)>,
68) -> impl Iterator<Item = (K, (&'a RefTarget, &'b RemoteRef))> {
69 iter_named_pairs(
70 refs1,
71 refs2,
72 || RefTarget::absent_ref(),
73 || RemoteRef::absent_ref(),
74 )
75}
76
77/// Compares `ids1` and `ids2` commit ids, yields entry if they differ.
78///
79/// `ids1` and `ids2` must be sorted by `K`.
80pub fn diff_named_commit_ids<'a, 'b, K: Ord>(
81 ids1: impl IntoIterator<Item = (K, &'a CommitId)>,
82 ids2: impl IntoIterator<Item = (K, &'b CommitId)>,
83) -> impl Iterator<Item = (K, (Option<&'a CommitId>, Option<&'b CommitId>))> {
84 iter_named_pairs(
85 ids1.into_iter().map(|(k, v)| (k, Some(v))),
86 ids2.into_iter().map(|(k, v)| (k, Some(v))),
87 || None,
88 || None,
89 )
90 .filter(|(_, (target1, target2))| target1 != target2)
91}
92
93fn iter_named_pairs<K: Ord, V1, V2>(
94 refs1: impl IntoIterator<Item = (K, V1)>,
95 refs2: impl IntoIterator<Item = (K, V2)>,
96 absent_ref1: impl Fn() -> V1,
97 absent_ref2: impl Fn() -> V2,
98) -> impl Iterator<Item = (K, (V1, V2))> {
99 itertools::merge_join_by(refs1, refs2, |(name1, _), (name2, _)| name1.cmp(name2)).map(
100 move |entry| match entry {
101 EitherOrBoth::Both((name, target1), (_, target2)) => (name, (target1, target2)),
102 EitherOrBoth::Left((name, target1)) => (name, (target1, absent_ref2())),
103 EitherOrBoth::Right((name, target2)) => (name, (absent_ref1(), target2)),
104 },
105 )
106}
107
108pub fn merge_ref_targets(
109 index: &dyn Index,
110 left: &RefTarget,
111 base: &RefTarget,
112 right: &RefTarget,
113) -> RefTarget {
114 if let Some(&resolved) = trivial_merge(&[left, base, right]) {
115 return resolved.clone();
116 }
117
118 let mut merge = Merge::from_vec(vec![
119 left.as_merge().clone(),
120 base.as_merge().clone(),
121 right.as_merge().clone(),
122 ])
123 .flatten()
124 .simplify();
125 // Suppose left = [A - C + B], base = [B], right = [A], the merge result is
126 // [A - C + A], which can now be trivially resolved.
127 if let Some(resolved) = merge.resolve_trivial() {
128 RefTarget::resolved(resolved.clone())
129 } else {
130 merge_ref_targets_non_trivial(index, &mut merge);
131 // TODO: Maybe better to try resolve_trivial() again, but the result is
132 // unreliable since merge_ref_targets_non_trivial() is order dependent.
133 RefTarget::from_merge(merge)
134 }
135}
136
137pub fn merge_remote_refs(
138 index: &dyn Index,
139 left: &RemoteRef,
140 base: &RemoteRef,
141 right: &RemoteRef,
142) -> RemoteRef {
143 // Just merge target and state fields separately. Strictly speaking, merging
144 // target-only change and state-only change shouldn't automatically mark the
145 // new target as tracking. However, many faulty merges will end up in local
146 // or remote target conflicts (since fast-forwardable move can be safely
147 // "tracked"), and the conflicts will require user intervention anyway. So
148 // there wouldn't be much reason to handle these merges precisely.
149 let target = merge_ref_targets(index, &left.target, &base.target, &right.target);
150 // Merged state shouldn't conflict atm since we only have two states, but if
151 // it does, keep the original state. The choice is arbitrary.
152 let state = *trivial_merge(&[left.state, base.state, right.state]).unwrap_or(&base.state);
153 RemoteRef { target, state }
154}
155
156fn merge_ref_targets_non_trivial(index: &dyn Index, conflict: &mut Merge<Option<CommitId>>) {
157 while let Some((remove_index, add_index)) = find_pair_to_remove(index, conflict) {
158 conflict.swap_remove(remove_index, add_index);
159 }
160}
161
162fn find_pair_to_remove(
163 index: &dyn Index,
164 conflict: &Merge<Option<CommitId>>,
165) -> Option<(usize, usize)> {
166 // If a "remove" is an ancestor of two different "adds" and one of the
167 // "adds" is an ancestor of the other, then pick the descendant.
168 for (add_index1, add1) in conflict.adds().enumerate() {
169 for (add_index2, add2) in conflict.adds().enumerate().skip(add_index1 + 1) {
170 // TODO: Instead of relying on the list order, maybe ((add1, add2), remove)
171 // combination should be somehow weighted?
172 let (add_index, add_id) = match (add1, add2) {
173 (Some(id1), Some(id2)) if id1 == id2 => (add_index1, id1),
174 (Some(id1), Some(id2)) if index.is_ancestor(id1, id2) => (add_index1, id1),
175 (Some(id1), Some(id2)) if index.is_ancestor(id2, id1) => (add_index2, id2),
176 _ => continue,
177 };
178 if let Some(remove_index) = conflict.removes().position(|remove| match remove {
179 Some(id) => index.is_ancestor(id, add_id),
180 None => true, // Absent ref can be considered a root
181 }) {
182 return Some((remove_index, add_index));
183 }
184 }
185 }
186
187 None
188}
189
190/// Owned remote bookmark or tag name.
191///
192/// This type can be displayed in `{name}@{remote}` form, with quoting and
193/// escaping if necessary.
194#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
195pub struct RemoteRefSymbolBuf {
196 /// Local name.
197 pub name: String,
198 /// Remote name.
199 pub remote: String,
200}
201
202impl RemoteRefSymbolBuf {
203 /// Converts to reference type.
204 pub fn as_ref(&self) -> RemoteRefSymbol<'_> {
205 RemoteRefSymbol {
206 name: &self.name,
207 remote: &self.remote,
208 }
209 }
210}
211
212/// Borrowed remote bookmark or tag name.
213///
214/// This type can be displayed in `{name}@{remote}` form, with quoting and
215/// escaping if necessary.
216#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
217pub struct RemoteRefSymbol<'a> {
218 /// Local name.
219 pub name: &'a str,
220 /// Remote name.
221 pub remote: &'a str,
222}
223
224impl RemoteRefSymbol<'_> {
225 /// Converts to owned type.
226 pub fn to_owned(self) -> RemoteRefSymbolBuf {
227 RemoteRefSymbolBuf {
228 name: self.name.to_owned(),
229 remote: self.remote.to_owned(),
230 }
231 }
232}
233
234impl From<RemoteRefSymbol<'_>> for RemoteRefSymbolBuf {
235 fn from(value: RemoteRefSymbol<'_>) -> Self {
236 value.to_owned()
237 }
238}
239
240impl PartialEq<RemoteRefSymbol<'_>> for RemoteRefSymbolBuf {
241 fn eq(&self, other: &RemoteRefSymbol) -> bool {
242 self.as_ref() == *other
243 }
244}
245
246impl PartialEq<RemoteRefSymbol<'_>> for &RemoteRefSymbolBuf {
247 fn eq(&self, other: &RemoteRefSymbol) -> bool {
248 self.as_ref() == *other
249 }
250}
251
252impl PartialEq<RemoteRefSymbolBuf> for RemoteRefSymbol<'_> {
253 fn eq(&self, other: &RemoteRefSymbolBuf) -> bool {
254 *self == other.as_ref()
255 }
256}
257
258impl PartialEq<&RemoteRefSymbolBuf> for RemoteRefSymbol<'_> {
259 fn eq(&self, other: &&RemoteRefSymbolBuf) -> bool {
260 *self == other.as_ref()
261 }
262}
263
264impl Display for RemoteRefSymbolBuf {
265 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
266 Display::fmt(&self.as_ref(), f)
267 }
268}
269
270impl Display for RemoteRefSymbol<'_> {
271 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272 let RemoteRefSymbol { name, remote } = self;
273 f.pad(&revset::format_remote_symbol(name, remote))
274 }
275}
276
277/// Pair of local and remote targets.
278#[derive(Clone, Copy, Debug, Eq, PartialEq)]
279pub struct LocalAndRemoteRef<'a> {
280 pub local_target: &'a RefTarget,
281 pub remote_ref: &'a RemoteRef,
282}
283
284#[derive(Debug, PartialEq, Eq, Clone, Hash)]
285pub struct BookmarkPushUpdate {
286 pub old_target: Option<CommitId>,
287 pub new_target: Option<CommitId>,
288}
289
290#[derive(Debug, PartialEq, Eq, Clone)]
291pub enum BookmarkPushAction {
292 Update(BookmarkPushUpdate),
293 AlreadyMatches,
294 LocalConflicted,
295 RemoteConflicted,
296 RemoteUntracked,
297}
298
299/// Figure out what changes (if any) need to be made to the remote when pushing
300/// this bookmark.
301pub fn classify_bookmark_push_action(targets: LocalAndRemoteRef) -> BookmarkPushAction {
302 let local_target = targets.local_target;
303 let remote_target = targets.remote_ref.tracking_target();
304 if local_target == remote_target {
305 BookmarkPushAction::AlreadyMatches
306 } else if local_target.has_conflict() {
307 BookmarkPushAction::LocalConflicted
308 } else if remote_target.has_conflict() {
309 BookmarkPushAction::RemoteConflicted
310 } else if targets.remote_ref.is_present() && !targets.remote_ref.is_tracking() {
311 BookmarkPushAction::RemoteUntracked
312 } else {
313 BookmarkPushAction::Update(BookmarkPushUpdate {
314 old_target: remote_target.as_normal().cloned(),
315 new_target: local_target.as_normal().cloned(),
316 })
317 }
318}
319
320#[cfg(test)]
321mod tests {
322 use super::*;
323 use crate::op_store::RemoteRefState;
324
325 fn new_remote_ref(target: RefTarget) -> RemoteRef {
326 RemoteRef {
327 target,
328 state: RemoteRefState::New,
329 }
330 }
331
332 fn tracking_remote_ref(target: RefTarget) -> RemoteRef {
333 RemoteRef {
334 target,
335 state: RemoteRefState::Tracking,
336 }
337 }
338
339 #[test]
340 fn test_classify_bookmark_push_action_unchanged() {
341 let commit_id1 = CommitId::from_hex("11");
342 let targets = LocalAndRemoteRef {
343 local_target: &RefTarget::normal(commit_id1.clone()),
344 remote_ref: &tracking_remote_ref(RefTarget::normal(commit_id1)),
345 };
346 assert_eq!(
347 classify_bookmark_push_action(targets),
348 BookmarkPushAction::AlreadyMatches
349 );
350 }
351
352 #[test]
353 fn test_classify_bookmark_push_action_added() {
354 let commit_id1 = CommitId::from_hex("11");
355 let targets = LocalAndRemoteRef {
356 local_target: &RefTarget::normal(commit_id1.clone()),
357 remote_ref: RemoteRef::absent_ref(),
358 };
359 assert_eq!(
360 classify_bookmark_push_action(targets),
361 BookmarkPushAction::Update(BookmarkPushUpdate {
362 old_target: None,
363 new_target: Some(commit_id1),
364 })
365 );
366 }
367
368 #[test]
369 fn test_classify_bookmark_push_action_removed() {
370 let commit_id1 = CommitId::from_hex("11");
371 let targets = LocalAndRemoteRef {
372 local_target: RefTarget::absent_ref(),
373 remote_ref: &tracking_remote_ref(RefTarget::normal(commit_id1.clone())),
374 };
375 assert_eq!(
376 classify_bookmark_push_action(targets),
377 BookmarkPushAction::Update(BookmarkPushUpdate {
378 old_target: Some(commit_id1),
379 new_target: None,
380 })
381 );
382 }
383
384 #[test]
385 fn test_classify_bookmark_push_action_updated() {
386 let commit_id1 = CommitId::from_hex("11");
387 let commit_id2 = CommitId::from_hex("22");
388 let targets = LocalAndRemoteRef {
389 local_target: &RefTarget::normal(commit_id2.clone()),
390 remote_ref: &tracking_remote_ref(RefTarget::normal(commit_id1.clone())),
391 };
392 assert_eq!(
393 classify_bookmark_push_action(targets),
394 BookmarkPushAction::Update(BookmarkPushUpdate {
395 old_target: Some(commit_id1),
396 new_target: Some(commit_id2),
397 })
398 );
399 }
400
401 #[test]
402 fn test_classify_bookmark_push_action_removed_untracked() {
403 // This is not RemoteUntracked error since non-tracking remote bookmarks
404 // have no relation to local bookmarks, and there's nothing to push.
405 let commit_id1 = CommitId::from_hex("11");
406 let targets = LocalAndRemoteRef {
407 local_target: RefTarget::absent_ref(),
408 remote_ref: &new_remote_ref(RefTarget::normal(commit_id1.clone())),
409 };
410 assert_eq!(
411 classify_bookmark_push_action(targets),
412 BookmarkPushAction::AlreadyMatches
413 );
414 }
415
416 #[test]
417 fn test_classify_bookmark_push_action_updated_untracked() {
418 let commit_id1 = CommitId::from_hex("11");
419 let commit_id2 = CommitId::from_hex("22");
420 let targets = LocalAndRemoteRef {
421 local_target: &RefTarget::normal(commit_id2.clone()),
422 remote_ref: &new_remote_ref(RefTarget::normal(commit_id1.clone())),
423 };
424 assert_eq!(
425 classify_bookmark_push_action(targets),
426 BookmarkPushAction::RemoteUntracked
427 );
428 }
429
430 #[test]
431 fn test_classify_bookmark_push_action_local_conflicted() {
432 let commit_id1 = CommitId::from_hex("11");
433 let commit_id2 = CommitId::from_hex("22");
434 let targets = LocalAndRemoteRef {
435 local_target: &RefTarget::from_legacy_form([], [commit_id1.clone(), commit_id2]),
436 remote_ref: &tracking_remote_ref(RefTarget::normal(commit_id1)),
437 };
438 assert_eq!(
439 classify_bookmark_push_action(targets),
440 BookmarkPushAction::LocalConflicted
441 );
442 }
443
444 #[test]
445 fn test_classify_bookmark_push_action_remote_conflicted() {
446 let commit_id1 = CommitId::from_hex("11");
447 let commit_id2 = CommitId::from_hex("22");
448 let targets = LocalAndRemoteRef {
449 local_target: &RefTarget::normal(commit_id1.clone()),
450 remote_ref: &tracking_remote_ref(RefTarget::from_legacy_form(
451 [],
452 [commit_id1, commit_id2],
453 )),
454 };
455 assert_eq!(
456 classify_bookmark_push_action(targets),
457 BookmarkPushAction::RemoteConflicted
458 );
459 }
460}