jujutsu_lib/
refs.rs

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
15use crate::backend::CommitId;
16use crate::index::Index;
17use crate::op_store::{BranchTarget, RefTarget};
18
19pub fn merge_ref_targets(
20    index: &dyn Index,
21    left: Option<&RefTarget>,
22    base: Option<&RefTarget>,
23    right: Option<&RefTarget>,
24) -> Option<RefTarget> {
25    if left == base || left == right {
26        right.cloned()
27    } else if base == right {
28        left.cloned()
29    } else {
30        let mut adds = vec![];
31        let mut removes = vec![];
32        if let Some(left) = left {
33            adds.extend(left.adds());
34            removes.extend(left.removes());
35        }
36        if let Some(base) = base {
37            // Note that these are backwards (because the base is subtracted).
38            adds.extend(base.removes());
39            removes.extend(base.adds());
40        }
41        if let Some(right) = right {
42            adds.extend(right.adds());
43            removes.extend(right.removes());
44        }
45
46        while let Some((maybe_remove_index, add_index)) =
47            find_pair_to_remove(index, &adds, &removes)
48        {
49            if let Some(remove_index) = maybe_remove_index {
50                removes.remove(remove_index);
51            }
52            adds.remove(add_index);
53        }
54
55        if adds.is_empty() {
56            None
57        } else if adds.len() == 1 && removes.is_empty() {
58            Some(RefTarget::Normal(adds[0].clone()))
59        } else {
60            Some(RefTarget::Conflict { removes, adds })
61        }
62    }
63}
64
65fn find_pair_to_remove(
66    index: &dyn Index,
67    adds: &[CommitId],
68    removes: &[CommitId],
69) -> Option<(Option<usize>, usize)> {
70    // Removes pairs of matching adds and removes.
71    for (add_index, add) in adds.iter().enumerate() {
72        for (remove_index, remove) in removes.iter().enumerate() {
73            if add == remove {
74                return Some((Some(remove_index), add_index));
75            }
76        }
77    }
78
79    // If a "remove" is an ancestor of two different "adds" and one of the
80    // "adds" is an ancestor of the other, then pick the descendant.
81    for (add_index1, add1) in adds.iter().enumerate() {
82        for (add_index2, add2) in adds.iter().enumerate().skip(add_index1 + 1) {
83            let first_add_is_ancestor;
84            if add1 == add2 || index.is_ancestor(add1, add2) {
85                first_add_is_ancestor = true;
86            } else if index.is_ancestor(add2, add1) {
87                first_add_is_ancestor = false;
88            } else {
89                continue;
90            }
91            if removes.is_empty() {
92                if first_add_is_ancestor {
93                    return Some((None, add_index1));
94                } else {
95                    return Some((None, add_index2));
96                }
97            }
98            for (remove_index, remove) in removes.iter().enumerate() {
99                if first_add_is_ancestor && index.is_ancestor(remove, add1) {
100                    return Some((Some(remove_index), add_index1));
101                } else if !first_add_is_ancestor && index.is_ancestor(remove, add2) {
102                    return Some((Some(remove_index), add_index2));
103                }
104            }
105        }
106    }
107
108    None
109}
110
111#[derive(Debug, PartialEq, Eq, Clone, Hash)]
112pub struct BranchPushUpdate {
113    pub old_target: Option<CommitId>,
114    pub new_target: Option<CommitId>,
115}
116
117#[derive(Debug, PartialEq, Eq, Clone)]
118pub enum BranchPushAction {
119    Update(BranchPushUpdate),
120    AlreadyMatches,
121    LocalConflicted,
122    RemoteConflicted,
123}
124
125/// Figure out what changes (if any) need to be made to the remote when pushing
126/// this branch.
127pub fn classify_branch_push_action(
128    branch_target: &BranchTarget,
129    remote_name: &str,
130) -> BranchPushAction {
131    let maybe_remote_target = branch_target.remote_targets.get(remote_name);
132    if branch_target.local_target.as_ref() == maybe_remote_target {
133        return BranchPushAction::AlreadyMatches;
134    }
135
136    match (&maybe_remote_target, &branch_target.local_target) {
137        (_, Some(RefTarget::Conflict { .. })) => BranchPushAction::LocalConflicted,
138        (Some(RefTarget::Conflict { .. }), _) => BranchPushAction::RemoteConflicted,
139        (Some(RefTarget::Normal(old_target)), Some(RefTarget::Normal(new_target))) => {
140            BranchPushAction::Update(BranchPushUpdate {
141                old_target: Some(old_target.clone()),
142                new_target: Some(new_target.clone()),
143            })
144        }
145        (Some(RefTarget::Normal(old_target)), None) => BranchPushAction::Update(BranchPushUpdate {
146            old_target: Some(old_target.clone()),
147            new_target: None,
148        }),
149        (None, Some(RefTarget::Normal(new_target))) => BranchPushAction::Update(BranchPushUpdate {
150            old_target: None,
151            new_target: Some(new_target.clone()),
152        }),
153        (None, None) => {
154            panic!("Unexpected branch doesn't exist anywhere")
155        }
156    }
157}
158
159#[cfg(test)]
160mod tests {
161    use maplit::btreemap;
162
163    use super::*;
164    use crate::backend::ObjectId;
165
166    #[test]
167    fn test_classify_branch_push_action_unchanged() {
168        let commit_id1 = CommitId::from_hex("11");
169        let branch = BranchTarget {
170            local_target: Some(RefTarget::Normal(commit_id1.clone())),
171            remote_targets: btreemap! {
172                "origin".to_string() => RefTarget::Normal(commit_id1)
173            },
174        };
175        assert_eq!(
176            classify_branch_push_action(&branch, "origin"),
177            BranchPushAction::AlreadyMatches
178        );
179    }
180
181    #[test]
182    fn test_classify_branch_push_action_added() {
183        let commit_id1 = CommitId::from_hex("11");
184        let branch = BranchTarget {
185            local_target: Some(RefTarget::Normal(commit_id1.clone())),
186            remote_targets: btreemap! {},
187        };
188        assert_eq!(
189            classify_branch_push_action(&branch, "origin"),
190            BranchPushAction::Update(BranchPushUpdate {
191                old_target: None,
192                new_target: Some(commit_id1),
193            })
194        );
195    }
196
197    #[test]
198    fn test_classify_branch_push_action_removed() {
199        let commit_id1 = CommitId::from_hex("11");
200        let branch = BranchTarget {
201            local_target: None,
202            remote_targets: btreemap! {
203                "origin".to_string() => RefTarget::Normal(commit_id1.clone())
204            },
205        };
206        assert_eq!(
207            classify_branch_push_action(&branch, "origin"),
208            BranchPushAction::Update(BranchPushUpdate {
209                old_target: Some(commit_id1),
210                new_target: None,
211            })
212        );
213    }
214
215    #[test]
216    fn test_classify_branch_push_action_updated() {
217        let commit_id1 = CommitId::from_hex("11");
218        let commit_id2 = CommitId::from_hex("22");
219        let branch = BranchTarget {
220            local_target: Some(RefTarget::Normal(commit_id2.clone())),
221            remote_targets: btreemap! {
222                "origin".to_string() => RefTarget::Normal(commit_id1.clone())
223            },
224        };
225        assert_eq!(
226            classify_branch_push_action(&branch, "origin"),
227            BranchPushAction::Update(BranchPushUpdate {
228                old_target: Some(commit_id1),
229                new_target: Some(commit_id2),
230            })
231        );
232    }
233
234    #[test]
235    fn test_classify_branch_push_action_local_conflicted() {
236        let commit_id1 = CommitId::from_hex("11");
237        let commit_id2 = CommitId::from_hex("22");
238        let branch = BranchTarget {
239            local_target: Some(RefTarget::Conflict {
240                removes: vec![],
241                adds: vec![commit_id1.clone(), commit_id2],
242            }),
243            remote_targets: btreemap! {
244                "origin".to_string() => RefTarget::Normal(commit_id1)
245            },
246        };
247        assert_eq!(
248            classify_branch_push_action(&branch, "origin"),
249            BranchPushAction::LocalConflicted
250        );
251    }
252
253    #[test]
254    fn test_classify_branch_push_action_remote_conflicted() {
255        let commit_id1 = CommitId::from_hex("11");
256        let commit_id2 = CommitId::from_hex("22");
257        let branch = BranchTarget {
258            local_target: Some(RefTarget::Normal(commit_id1.clone())),
259            remote_targets: btreemap! {
260                "origin".to_string() => RefTarget::Conflict {
261                removes: vec![],
262                adds: vec![commit_id1, commit_id2]
263            }
264            },
265        };
266        assert_eq!(
267            classify_branch_push_action(&branch, "origin"),
268            BranchPushAction::RemoteConflicted
269        );
270    }
271}
jujutsu_lib/refs.rs

jujutsu_lib/
refs.rs
