1use std::collections::BTreeSet;
4
5use smallvec::smallvec;
6
7use crate::db::{CommitDraft, Db};
8use crate::entry::{Op, Value};
9use crate::error::{Error, Result};
10use crate::id::CommitId;
11use crate::store::Root;
12use crate::txn::apply_ops;
13
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
16pub enum MergePolicy {
17 #[default]
20 Fail,
21 Ours,
23 Theirs,
25}
26
27impl MergePolicy {
28 pub fn parse(s: &str) -> Option<Self> {
30 match s.to_ascii_lowercase().as_str() {
31 "fail" => Some(MergePolicy::Fail),
32 "ours" => Some(MergePolicy::Ours),
33 "theirs" => Some(MergePolicy::Theirs),
34 _ => None,
35 }
36 }
37
38 pub fn as_str(self) -> &'static str {
40 match self {
41 MergePolicy::Fail => "fail",
42 MergePolicy::Ours => "ours",
43 MergePolicy::Theirs => "theirs",
44 }
45 }
46}
47
48#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub enum MergeKind {
51 UpToDate,
53 FastForward,
55 Merged,
57}
58
59impl MergeKind {
60 pub fn as_str(self) -> &'static str {
65 match self {
66 MergeKind::UpToDate => "up-to-date",
67 MergeKind::FastForward => "fast-forward",
68 MergeKind::Merged => "merged",
69 }
70 }
71}
72
73#[derive(Debug, Clone)]
75pub struct MergeOutcome {
76 pub target: String,
78 pub source: String,
80 pub head: CommitId,
82 pub base: CommitId,
84 pub kind: MergeKind,
86 pub changed: Vec<String>,
88 pub conflicts: Vec<String>,
91}
92
93impl Db {
94 pub fn merge(&self, source: &str, target: &str, policy: MergePolicy) -> Result<MergeOutcome> {
101 let target_handle = self.branch_handle(target)?;
104 let _writing = target_handle.writer.lock();
105
106 let source_head = self.head(source)?;
107 let target_head = self.head(target)?;
108
109 let base = self
110 .common_ancestor(target_head, source_head)
111 .ok_or_else(|| Error::NoCommonAncestor {
112 from_branch: source.to_owned(),
113 into_branch: target.to_owned(),
114 })?;
115
116 if base == source_head {
117 return Ok(MergeOutcome {
119 target: target.to_owned(),
120 source: source.to_owned(),
121 head: target_head,
122 base,
123 kind: MergeKind::UpToDate,
124 changed: Vec::new(),
125 conflicts: Vec::new(),
126 });
127 }
128
129 let base_root = self.commit(base)?.root.clone();
130 let ours = self.commit(target_head)?.root.clone();
131 let theirs = self.commit(source_head)?.root.clone();
132
133 if base == target_head {
134 let changed = crate::db::diff_roots(&ours, &theirs)
137 .into_iter()
138 .map(|c| c.key)
139 .collect();
140 let head = self.fast_forward(target, target_head, source_head)?;
141 return Ok(MergeOutcome {
142 target: target.to_owned(),
143 source: source.to_owned(),
144 head,
145 base,
146 kind: MergeKind::FastForward,
147 changed,
148 conflicts: Vec::new(),
149 });
150 }
151
152 let plan = plan_merge(&base_root, &ours, &theirs, policy);
153 if policy == MergePolicy::Fail && !plan.conflicts.is_empty() {
154 return Err(Error::MergeConflict {
155 keys: plan.conflicts,
156 });
157 }
158
159 if plan.ops.is_empty() {
160 return Ok(MergeOutcome {
164 target: target.to_owned(),
165 source: source.to_owned(),
166 head: target_head,
167 base,
168 kind: MergeKind::UpToDate,
169 changed: Vec::new(),
170 conflicts: plan.conflicts,
171 });
172 }
173
174 let seq = self.commit(target_head)?.seq + 1;
175 let mut root = ours;
176 apply_ops(&mut root, &plan.ops, seq);
177 let changed: Vec<String> = plan.ops.iter().map(|op| op.key().to_owned()).collect();
178
179 let head = self.commit_onto(
180 target,
181 target_head,
182 CommitDraft {
183 parents: smallvec![target_head, source_head],
184 root,
185 seq,
186 message: Some(format!(
187 "merge {source} into {target} ({})",
188 policy.as_str()
189 )),
190 ops: plan.ops,
191 },
192 )?;
193
194 Ok(MergeOutcome {
195 target: target.to_owned(),
196 source: source.to_owned(),
197 head,
198 base,
199 kind: MergeKind::Merged,
200 changed,
201 conflicts: plan.conflicts,
202 })
203 }
204}
205
206#[derive(Debug)]
207struct MergePlan {
208 ops: Vec<Op>,
210 conflicts: Vec<String>,
212}
213
214fn plan_merge(base: &Root, ours: &Root, theirs: &Root, policy: MergePolicy) -> MergePlan {
216 let mut candidates: BTreeSet<&String> = BTreeSet::new();
220 for (k, v) in base.iter() {
221 if ours.get(k).is_none_or(|o| !o.content_eq(v))
222 || theirs.get(k).is_none_or(|t| !t.content_eq(v))
223 {
224 candidates.insert(k);
225 }
226 }
227 for (k, v) in ours.iter() {
228 if base.get(k).is_none_or(|b| !b.content_eq(v)) {
229 candidates.insert(k);
230 }
231 }
232 for (k, v) in theirs.iter() {
233 if base.get(k).is_none_or(|b| !b.content_eq(v)) {
234 candidates.insert(k);
235 }
236 }
237
238 let mut ops = Vec::new();
239 let mut conflicts = Vec::new();
240
241 for key in candidates {
242 let b = base.get(key);
243 let o = ours.get(key);
244 let t = theirs.get(key);
245
246 let ours_changed = !same(b, o);
247 let theirs_changed = !same(b, t);
248
249 let take_theirs = match (ours_changed, theirs_changed) {
250 (false, true) => true,
252 (_, false) => false,
254 (true, true) => {
256 if same(o, t) {
257 false
258 } else {
259 conflicts.push(key.clone());
260 policy == MergePolicy::Theirs
261 }
262 }
263 };
264
265 if !take_theirs {
266 continue;
267 }
268 match t {
269 Some(entry) => ops.push(Op::Put {
270 key: key.clone(),
271 value: Value::from(entry.as_ref()),
272 }),
273 None => ops.push(Op::Delete { key: key.clone() }),
274 }
275 }
276
277 MergePlan { ops, conflicts }
278}
279
280fn same(
281 a: Option<&std::sync::Arc<crate::entry::Entry>>,
282 b: Option<&std::sync::Arc<crate::entry::Entry>>,
283) -> bool {
284 match (a, b) {
285 (None, None) => true,
286 (Some(x), Some(y)) => x.content_eq(y),
287 _ => false,
288 }
289}