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 itertools::EitherOrBoth;
18
19use crate::backend::CommitId;
20use crate::index::Index;
21use crate::merge::trivial_merge;
22use crate::merge::Merge;
23use crate::op_store::RefTarget;
24use crate::op_store::RemoteRef;
25
26/// Compares `refs1` and `refs2` targets, yields entry if they differ.
27///
28/// `refs1` and `refs2` must be sorted by `K`.
29pub fn diff_named_ref_targets<'a, 'b, K: Ord>(
30 refs1: impl IntoIterator<Item = (K, &'a RefTarget)>,
31 refs2: impl IntoIterator<Item = (K, &'b RefTarget)>,
32) -> impl Iterator<Item = (K, (&'a RefTarget, &'b RefTarget))> {
33 iter_named_pairs(
34 refs1,
35 refs2,
36 || RefTarget::absent_ref(),
37 || RefTarget::absent_ref(),
38 )
39 .filter(|(_, (target1, target2))| target1 != target2)
40}
41
42/// Compares remote `refs1` and `refs2` pairs, yields entry if they differ.
43///
44/// `refs1` and `refs2` must be sorted by `K`.
45pub fn diff_named_remote_refs<'a, 'b, K: Ord>(
46 refs1: impl IntoIterator<Item = (K, &'a RemoteRef)>,
47 refs2: impl IntoIterator<Item = (K, &'b RemoteRef)>,
48) -> impl Iterator<Item = (K, (&'a RemoteRef, &'b RemoteRef))> {
49 iter_named_pairs(
50 refs1,
51 refs2,
52 || RemoteRef::absent_ref(),
53 || RemoteRef::absent_ref(),
54 )
55 .filter(|(_, (ref1, ref2))| ref1 != ref2)
56}
57
58/// Iterates local `refs1` and remote `refs2` pairs by name.
59///
60/// `refs1` and `refs2` must be sorted by `K`.
61pub fn iter_named_local_remote_refs<'a, 'b, K: Ord>(
62 refs1: impl IntoIterator<Item = (K, &'a RefTarget)>,
63 refs2: impl IntoIterator<Item = (K, &'b RemoteRef)>,
64) -> impl Iterator<Item = (K, (&'a RefTarget, &'b RemoteRef))> {
65 iter_named_pairs(
66 refs1,
67 refs2,
68 || RefTarget::absent_ref(),
69 || RemoteRef::absent_ref(),
70 )
71}
72
73/// Compares `ids1` and `ids2` commit ids, yields entry if they differ.
74///
75/// `ids1` and `ids2` must be sorted by `K`.
76pub fn diff_named_commit_ids<'a, 'b, K: Ord>(
77 ids1: impl IntoIterator<Item = (K, &'a CommitId)>,
78 ids2: impl IntoIterator<Item = (K, &'b CommitId)>,
79) -> impl Iterator<Item = (K, (Option<&'a CommitId>, Option<&'b CommitId>))> {
80 iter_named_pairs(
81 ids1.into_iter().map(|(k, v)| (k, Some(v))),
82 ids2.into_iter().map(|(k, v)| (k, Some(v))),
83 || None,
84 || None,
85 )
86 .filter(|(_, (target1, target2))| target1 != target2)
87}
88
89fn iter_named_pairs<K: Ord, V1, V2>(
90 refs1: impl IntoIterator<Item = (K, V1)>,
91 refs2: impl IntoIterator<Item = (K, V2)>,
92 absent_ref1: impl Fn() -> V1,
93 absent_ref2: impl Fn() -> V2,
94) -> impl Iterator<Item = (K, (V1, V2))> {
95 itertools::merge_join_by(refs1, refs2, |(name1, _), (name2, _)| name1.cmp(name2)).map(
96 move |entry| match entry {
97 EitherOrBoth::Both((name, target1), (_, target2)) => (name, (target1, target2)),
98 EitherOrBoth::Left((name, target1)) => (name, (target1, absent_ref2())),
99 EitherOrBoth::Right((name, target2)) => (name, (absent_ref1(), target2)),
100 },
101 )
102}
103
104pub fn merge_ref_targets(
105 index: &dyn Index,
106 left: &RefTarget,
107 base: &RefTarget,
108 right: &RefTarget,
109) -> RefTarget {
110 if let Some(&resolved) = trivial_merge(&[left, base, right]) {
111 return resolved.clone();
112 }
113
114 let mut merge = Merge::from_vec(vec![
115 left.as_merge().clone(),
116 base.as_merge().clone(),
117 right.as_merge().clone(),
118 ])
119 .flatten()
120 .simplify();
121 // Suppose left = [A - C + B], base = [B], right = [A], the merge result is
122 // [A - C + A], which can now be trivially resolved.
123 if let Some(resolved) = merge.resolve_trivial() {
124 RefTarget::resolved(resolved.clone())
125 } else {
126 merge_ref_targets_non_trivial(index, &mut merge);
127 // TODO: Maybe better to try resolve_trivial() again, but the result is
128 // unreliable since merge_ref_targets_non_trivial() is order dependent.
129 RefTarget::from_merge(merge)
130 }
131}
132
133pub fn merge_remote_refs(
134 index: &dyn Index,
135 left: &RemoteRef,
136 base: &RemoteRef,
137 right: &RemoteRef,
138) -> RemoteRef {
139 // Just merge target and state fields separately. Strictly speaking, merging
140 // target-only change and state-only change shouldn't automatically mark the
141 // new target as tracking. However, many faulty merges will end up in local
142 // or remote target conflicts (since fast-forwardable move can be safely
143 // "tracked"), and the conflicts will require user intervention anyway. So
144 // there wouldn't be much reason to handle these merges precisely.
145 let target = merge_ref_targets(index, &left.target, &base.target, &right.target);
146 // Merged state shouldn't conflict atm since we only have two states, but if
147 // it does, keep the original state. The choice is arbitrary.
148 let state = *trivial_merge(&[left.state, base.state, right.state]).unwrap_or(&base.state);
149 RemoteRef { target, state }
150}
151
152fn merge_ref_targets_non_trivial(index: &dyn Index, conflict: &mut Merge<Option<CommitId>>) {
153 while let Some((remove_index, add_index)) = find_pair_to_remove(index, conflict) {
154 conflict.swap_remove(remove_index, add_index);
155 }
156}
157
158fn find_pair_to_remove(
159 index: &dyn Index,
160 conflict: &Merge<Option<CommitId>>,
161) -> Option<(usize, usize)> {
162 // If a "remove" is an ancestor of two different "adds" and one of the
163 // "adds" is an ancestor of the other, then pick the descendant.
164 for (add_index1, add1) in conflict.adds().enumerate() {
165 for (add_index2, add2) in conflict.adds().enumerate().skip(add_index1 + 1) {
166 // TODO: Instead of relying on the list order, maybe ((add1, add2), remove)
167 // combination should be somehow weighted?
168 let (add_index, add_id) = match (add1, add2) {
169 (Some(id1), Some(id2)) if id1 == id2 => (add_index1, id1),
170 (Some(id1), Some(id2)) if index.is_ancestor(id1, id2) => (add_index1, id1),
171 (Some(id1), Some(id2)) if index.is_ancestor(id2, id1) => (add_index2, id2),
172 _ => continue,
173 };
174 if let Some(remove_index) = conflict.removes().position(|remove| match remove {
175 Some(id) => index.is_ancestor(id, add_id),
176 None => true, // Absent ref can be considered a root
177 }) {
178 return Some((remove_index, add_index));
179 }
180 }
181 }
182
183 None
184}
185
186/// Pair of local and remote targets.
187#[derive(Clone, Copy, Debug, Eq, PartialEq)]
188pub struct LocalAndRemoteRef<'a> {
189 pub local_target: &'a RefTarget,
190 pub remote_ref: &'a RemoteRef,
191}
192
193#[derive(Debug, PartialEq, Eq, Clone, Hash)]
194pub struct BookmarkPushUpdate {
195 pub old_target: Option<CommitId>,
196 pub new_target: Option<CommitId>,
197}
198
199#[derive(Debug, PartialEq, Eq, Clone)]
200pub enum BookmarkPushAction {
201 Update(BookmarkPushUpdate),
202 AlreadyMatches,
203 LocalConflicted,
204 RemoteConflicted,
205 RemoteUntracked,
206}
207
208/// Figure out what changes (if any) need to be made to the remote when pushing
209/// this bookmark.
210pub fn classify_bookmark_push_action(targets: LocalAndRemoteRef) -> BookmarkPushAction {
211 let local_target = targets.local_target;
212 let remote_target = targets.remote_ref.tracked_target();
213 if local_target == remote_target {
214 BookmarkPushAction::AlreadyMatches
215 } else if local_target.has_conflict() {
216 BookmarkPushAction::LocalConflicted
217 } else if remote_target.has_conflict() {
218 BookmarkPushAction::RemoteConflicted
219 } else if targets.remote_ref.is_present() && !targets.remote_ref.is_tracked() {
220 BookmarkPushAction::RemoteUntracked
221 } else {
222 BookmarkPushAction::Update(BookmarkPushUpdate {
223 old_target: remote_target.as_normal().cloned(),
224 new_target: local_target.as_normal().cloned(),
225 })
226 }
227}
228
229#[cfg(test)]
230mod tests {
231 use super::*;
232 use crate::op_store::RemoteRefState;
233
234 fn new_remote_ref(target: RefTarget) -> RemoteRef {
235 RemoteRef {
236 target,
237 state: RemoteRefState::New,
238 }
239 }
240
241 fn tracked_remote_ref(target: RefTarget) -> RemoteRef {
242 RemoteRef {
243 target,
244 state: RemoteRefState::Tracked,
245 }
246 }
247
248 #[test]
249 fn test_classify_bookmark_push_action_unchanged() {
250 let commit_id1 = CommitId::from_hex("11");
251 let targets = LocalAndRemoteRef {
252 local_target: &RefTarget::normal(commit_id1.clone()),
253 remote_ref: &tracked_remote_ref(RefTarget::normal(commit_id1)),
254 };
255 assert_eq!(
256 classify_bookmark_push_action(targets),
257 BookmarkPushAction::AlreadyMatches
258 );
259 }
260
261 #[test]
262 fn test_classify_bookmark_push_action_added() {
263 let commit_id1 = CommitId::from_hex("11");
264 let targets = LocalAndRemoteRef {
265 local_target: &RefTarget::normal(commit_id1.clone()),
266 remote_ref: RemoteRef::absent_ref(),
267 };
268 assert_eq!(
269 classify_bookmark_push_action(targets),
270 BookmarkPushAction::Update(BookmarkPushUpdate {
271 old_target: None,
272 new_target: Some(commit_id1),
273 })
274 );
275 }
276
277 #[test]
278 fn test_classify_bookmark_push_action_removed() {
279 let commit_id1 = CommitId::from_hex("11");
280 let targets = LocalAndRemoteRef {
281 local_target: RefTarget::absent_ref(),
282 remote_ref: &tracked_remote_ref(RefTarget::normal(commit_id1.clone())),
283 };
284 assert_eq!(
285 classify_bookmark_push_action(targets),
286 BookmarkPushAction::Update(BookmarkPushUpdate {
287 old_target: Some(commit_id1),
288 new_target: None,
289 })
290 );
291 }
292
293 #[test]
294 fn test_classify_bookmark_push_action_updated() {
295 let commit_id1 = CommitId::from_hex("11");
296 let commit_id2 = CommitId::from_hex("22");
297 let targets = LocalAndRemoteRef {
298 local_target: &RefTarget::normal(commit_id2.clone()),
299 remote_ref: &tracked_remote_ref(RefTarget::normal(commit_id1.clone())),
300 };
301 assert_eq!(
302 classify_bookmark_push_action(targets),
303 BookmarkPushAction::Update(BookmarkPushUpdate {
304 old_target: Some(commit_id1),
305 new_target: Some(commit_id2),
306 })
307 );
308 }
309
310 #[test]
311 fn test_classify_bookmark_push_action_removed_untracked() {
312 // This is not RemoteUntracked error since non-tracking remote bookmarks
313 // have no relation to local bookmarks, and there's nothing to push.
314 let commit_id1 = CommitId::from_hex("11");
315 let targets = LocalAndRemoteRef {
316 local_target: RefTarget::absent_ref(),
317 remote_ref: &new_remote_ref(RefTarget::normal(commit_id1.clone())),
318 };
319 assert_eq!(
320 classify_bookmark_push_action(targets),
321 BookmarkPushAction::AlreadyMatches
322 );
323 }
324
325 #[test]
326 fn test_classify_bookmark_push_action_updated_untracked() {
327 let commit_id1 = CommitId::from_hex("11");
328 let commit_id2 = CommitId::from_hex("22");
329 let targets = LocalAndRemoteRef {
330 local_target: &RefTarget::normal(commit_id2.clone()),
331 remote_ref: &new_remote_ref(RefTarget::normal(commit_id1.clone())),
332 };
333 assert_eq!(
334 classify_bookmark_push_action(targets),
335 BookmarkPushAction::RemoteUntracked
336 );
337 }
338
339 #[test]
340 fn test_classify_bookmark_push_action_local_conflicted() {
341 let commit_id1 = CommitId::from_hex("11");
342 let commit_id2 = CommitId::from_hex("22");
343 let targets = LocalAndRemoteRef {
344 local_target: &RefTarget::from_legacy_form([], [commit_id1.clone(), commit_id2]),
345 remote_ref: &tracked_remote_ref(RefTarget::normal(commit_id1)),
346 };
347 assert_eq!(
348 classify_bookmark_push_action(targets),
349 BookmarkPushAction::LocalConflicted
350 );
351 }
352
353 #[test]
354 fn test_classify_bookmark_push_action_remote_conflicted() {
355 let commit_id1 = CommitId::from_hex("11");
356 let commit_id2 = CommitId::from_hex("22");
357 let targets = LocalAndRemoteRef {
358 local_target: &RefTarget::normal(commit_id1.clone()),
359 remote_ref: &tracked_remote_ref(RefTarget::from_legacy_form(
360 [],
361 [commit_id1, commit_id2],
362 )),
363 };
364 assert_eq!(
365 classify_bookmark_push_action(targets),
366 BookmarkPushAction::RemoteConflicted
367 );
368 }
369}