Skip to main content

memfork_core/
merge.rs

1//! Three-way merge at key level (DESIGN §4.2).
2
3use 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/// What to do with a key both branches changed (DESIGN §4.2).
15#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
16pub enum MergePolicy {
17    /// Change nothing and report the conflicting keys. The default: an agent
18    /// should have to say which side wins.
19    #[default]
20    Fail,
21    /// Keep the target branch's value.
22    Ours,
23    /// Take the source branch's value.
24    Theirs,
25}
26
27impl MergePolicy {
28    /// Parse `fail`, `ours` or `theirs`, case-insensitively.
29    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    /// The name this policy parses from.
39    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/// How a merge resolved.
49#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub enum MergeKind {
51    /// The source was already an ancestor of the target; nothing to do.
52    UpToDate,
53    /// The target had not moved since the fork, so its head simply advanced.
54    FastForward,
55    /// A merge commit with both heads as parents was created.
56    Merged,
57}
58
59impl MergeKind {
60    /// The name this outcome goes by, in the CLI, the tools and the bindings.
61    ///
62    /// One spelling in one place: three copies of this match drifted into
63    /// three different words the last time it was written out by hand.
64    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/// The result of a successful merge.
74#[derive(Debug, Clone)]
75pub struct MergeOutcome {
76    /// The branch that was merged into.
77    pub target: String,
78    /// The branch that was merged from.
79    pub source: String,
80    /// The target's head after the merge.
81    pub head: CommitId,
82    /// The common ancestor the three-way merge was computed against.
83    pub base: CommitId,
84    /// How the merge resolved.
85    pub kind: MergeKind,
86    /// Keys the merge changed on the target, sorted ascending.
87    pub changed: Vec<String>,
88    /// Keys both sides had changed, sorted ascending. Always empty under
89    /// [`MergePolicy::Fail`], which errors instead.
90    pub conflicts: Vec<String>,
91}
92
93impl Db {
94    /// Merge `source` into `target` against their common ancestor (DESIGN §4.2).
95    ///
96    /// A key is in conflict only when both sides changed it to different
97    /// content. Under [`MergePolicy::Fail`] a conflict returns
98    /// [`Error::MergeConflict`] with every conflicting key and changes
99    /// nothing at all.
100    pub fn merge(&self, source: &str, target: &str, policy: MergePolicy) -> Result<MergeOutcome> {
101        // A merge is a read-modify-write on the target, so it takes the
102        // target's turn at writing rather than racing single-key writes.
103        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            // Everything on the source is already in the target's history.
118            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            // The target has not moved since the fork: advance it. Nothing is
135            // recomputed, so this stays O(1) however large the branches are.
136            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            // Both sides made the same change, or only the target moved. There
161            // is still real history to record, so a merge commit is made below
162            // only when there is something to say; otherwise the target stands.
163            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    /// Changes to apply to the target, sorted ascending by key.
209    ops: Vec<Op>,
210    /// Keys both sides changed differently, sorted ascending.
211    conflicts: Vec<String>,
212}
213
214/// Compute the change set that folds `theirs` into `ours` relative to `base`.
215fn plan_merge(base: &Root, ours: &Root, theirs: &Root, policy: MergePolicy) -> MergePlan {
216    // The candidate set is every key that either side touched. Collected into
217    // a BTreeSet so the plan is emitted in ascending key order regardless of
218    // which side contributed the key.
219    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            // Only the source moved: take it.
251            (false, true) => true,
252            // Only the target moved, or neither did: leave the target alone.
253            (_, false) => false,
254            // Both moved. Identical changes are not a conflict.
255            (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}