| 1 | //! Three-way merges: of text (line by line) and of snapshots (file by file). |
| 2 | //! |
| 3 | //! Used to rebuild a change on a main that has moved since the change was made: each step's |
| 4 | //! edits (from the step before it to the step) are replayed onto the newer snapshot. |
| 5 | |
| 6 | use crate::diff::{diff, lines, Op}; |
| 7 | use crate::objects::{self, Entry, Id, Kind, Objects}; |
| 8 | use std::collections::BTreeMap; |
| 9 | |
| 10 | /// Base line index → index of the same line in `other`, where the diff keeps it. |
| 11 | fn alignment(base: &[&str], other: &[&str]) -> Vec<Option<usize>> { |
| 12 | let mut map = vec![None; base.len()]; |
| 13 | let (mut i, mut j) = (0, 0); |
| 14 | for (op, _) in diff(base, other) { |
| 15 | match op { |
| 16 | Op::Same => { |
| 17 | map[i] = Some(j); |
| 18 | i += 1; |
| 19 | j += 1; |
| 20 | } |
| 21 | Op::Del => i += 1, |
| 22 | Op::Add => j += 1, |
| 23 | } |
| 24 | } |
| 25 | map |
| 26 | } |
| 27 | |
| 28 | /// Merge two edits of `base`. Ok(text), or Err(number of conflicting regions). |
| 29 | pub fn merge_text(base: &str, ours: &str, theirs: &str) -> Result<String, usize> { |
| 30 | if ours == theirs || theirs == base { |
| 31 | return Ok(ours.to_string()); |
| 32 | } |
| 33 | if ours == base { |
| 34 | return Ok(theirs.to_string()); |
| 35 | } |
| 36 | let (b, a, t) = (lines(base), lines(ours), lines(theirs)); |
| 37 | let (ia, it) = (alignment(&b, &a), alignment(&b, &t)); |
| 38 | let mut out: Vec<&str> = Vec::new(); |
| 39 | let mut conflicts = 0; |
| 40 | let (mut i, mut ja, mut jt) = (0usize, 0usize, 0usize); |
| 41 | loop { |
| 42 | // The next base line both sides kept: everything before it is one unstable chunk. |
| 43 | let sync = (i..b.len()).find(|&k| matches!((ia[k], it[k]), (Some(x), Some(y)) if x >= ja && y >= jt)); |
| 44 | let (k, ka, kt) = match sync { |
| 45 | Some(k) => (k, ia[k].unwrap(), it[k].unwrap()), |
| 46 | None => (b.len(), a.len(), t.len()), |
| 47 | }; |
| 48 | let (cb, ca, ct) = (&b[i..k], &a[ja..ka], &t[jt..kt]); |
| 49 | if !(cb.is_empty() && ca.is_empty() && ct.is_empty()) { |
| 50 | if ca == cb { |
| 51 | out.extend_from_slice(ct); |
| 52 | } else if ct == cb || ca == ct { |
| 53 | out.extend_from_slice(ca); |
| 54 | } else { |
| 55 | conflicts += 1; |
| 56 | } |
| 57 | } |
| 58 | if sync.is_none() { |
| 59 | break; |
| 60 | } |
| 61 | out.push(b[k]); |
| 62 | i = k + 1; |
| 63 | ja = ka + 1; |
| 64 | jt = kt + 1; |
| 65 | } |
| 66 | if conflicts > 0 { |
| 67 | return Err(conflicts); |
| 68 | } |
| 69 | // The trailing newline merges like everything else. |
| 70 | let nl = |s: &str| s.ends_with('\n'); |
| 71 | let ends = if nl(ours) == nl(base) { nl(theirs) } else { nl(ours) }; |
| 72 | let mut text = out.join("\n"); |
| 73 | if ends && !out.is_empty() { |
| 74 | text.push('\n'); |
| 75 | } |
| 76 | Ok(text) |
| 77 | } |
| 78 | |
| 79 | type Files = BTreeMap<String, (Kind, Id)>; |
| 80 | |
| 81 | fn files(objects: &Objects, tree: &Id) -> objects::Result<Files> { |
| 82 | Ok(objects.flatten(tree)?.into_iter().map(|(p, k, i)| (p, (k, i))).collect()) |
| 83 | } |
| 84 | |
| 85 | /// One three-way choice: unchanged on one side means take the other. |
| 86 | fn pick<T: PartialEq + Clone>(base: &T, ours: &T, theirs: &T) -> Option<T> { |
| 87 | if ours == theirs || theirs == base { |
| 88 | Some(ours.clone()) |
| 89 | } else if ours == base { |
| 90 | Some(theirs.clone()) |
| 91 | } else { |
| 92 | None |
| 93 | } |
| 94 | } |
| 95 | |
| 96 | #[derive(Debug, PartialEq)] |
| 97 | pub enum Outcome { |
| 98 | Merged(Id), |
| 99 | /// Paths that changed on both sides in ways that can't be combined. |
| 100 | Conflicts(Vec<String>), |
| 101 | } |
| 102 | |
| 103 | /// Merge the edits `base → ours` and `base → theirs` into one snapshot. |
| 104 | pub fn merge_trees(objects: &Objects, base: &Id, ours: &Id, theirs: &Id) -> objects::Result<Outcome> { |
| 105 | if ours == theirs || theirs == base { |
| 106 | return Ok(Outcome::Merged(*ours)); |
| 107 | } |
| 108 | if ours == base { |
| 109 | return Ok(Outcome::Merged(*theirs)); |
| 110 | } |
| 111 | let (fb, fo, ft) = (files(objects, base)?, files(objects, ours)?, files(objects, theirs)?); |
| 112 | let mut paths: Vec<&String> = fb.keys().chain(fo.keys()).chain(ft.keys()).collect(); |
| 113 | paths.sort(); |
| 114 | paths.dedup(); |
| 115 | |
| 116 | let mut result: Files = BTreeMap::new(); |
| 117 | let mut conflicts = Vec::new(); |
| 118 | for path in paths { |
| 119 | let (b, o, t) = (fb.get(path).copied(), fo.get(path).copied(), ft.get(path).copied()); |
| 120 | if let Some(choice) = pick(&b, &o, &t) { |
| 121 | if let Some(f) = choice { |
| 122 | result.insert(path.clone(), f); |
| 123 | } |
| 124 | continue; |
| 125 | } |
| 126 | // Changed on both sides, differently. Combinable only if both still have a regular |
| 127 | // file there and the contents merge as text. |
| 128 | let merged = (|| -> objects::Result<Option<(Kind, Id)>> { |
| 129 | let (Some((ko, io)), Some((kt, it))) = (o, t) else { return Ok(None) }; |
| 130 | let regular = |k: Kind| matches!(k, Kind::File | Kind::Exec); |
| 131 | if !regular(ko) || !regular(kt) { |
| 132 | return Ok(None); |
| 133 | } |
| 134 | let kb = b.map(|(k, _)| k).unwrap_or(ko); |
| 135 | let Some(kind) = pick(&kb, &ko, &kt) else { return Ok(None) }; |
| 136 | let read = |id: &Id| objects.get_blob(id).map(|bytes| String::from_utf8(bytes).ok()); |
| 137 | let base_text = match b { |
| 138 | Some((_, ib)) => read(&ib)?, |
| 139 | None => Some(String::new()), |
| 140 | }; |
| 141 | let (Some(bt), Some(ot), Some(tt)) = (base_text, read(&io)?, read(&it)?) else { return Ok(None) }; |
| 142 | match merge_text(&bt, &ot, &tt) { |
| 143 | Ok(text) => Ok(Some((kind, objects.put_blob(text.as_bytes())?))), |
| 144 | Err(_) => Ok(None), |
| 145 | } |
| 146 | })()?; |
| 147 | match merged { |
| 148 | Some(f) => { |
| 149 | result.insert(path.clone(), f); |
| 150 | } |
| 151 | None => conflicts.push(path.clone()), |
| 152 | } |
| 153 | } |
| 154 | // A file on one side where the other has a directory. |
| 155 | for path in result.keys() { |
| 156 | let dir = format!("{path}/"); |
| 157 | if result.range(dir.clone()..).next().is_some_and(|(p, _)| p.starts_with(&dir)) { |
| 158 | conflicts.push(path.clone()); |
| 159 | } |
| 160 | } |
| 161 | if !conflicts.is_empty() { |
| 162 | conflicts.sort(); |
| 163 | conflicts.dedup(); |
| 164 | return Ok(Outcome::Conflicts(conflicts)); |
| 165 | } |
| 166 | Ok(Outcome::Merged(build_tree(objects, &result)?)) |
| 167 | } |
| 168 | |
| 169 | /// Store a nested tree for a flat path → file map. |
| 170 | pub fn build_tree(objects: &Objects, files: &Files) -> objects::Result<Id> { |
| 171 | #[derive(Default)] |
| 172 | struct Dir { |
| 173 | files: Vec<Entry>, |
| 174 | dirs: BTreeMap<String, Dir>, |
| 175 | } |
| 176 | let mut root = Dir::default(); |
| 177 | for (path, (kind, id)) in files { |
| 178 | let mut parts: Vec<&str> = path.split('/').collect(); |
| 179 | let name = parts.pop().unwrap(); |
| 180 | let mut dir = &mut root; |
| 181 | for p in parts { |
| 182 | dir = dir.dirs.entry(p.to_string()).or_default(); |
| 183 | } |
| 184 | dir.files.push(Entry { name: name.to_string(), kind: *kind, id: *id }); |
| 185 | } |
| 186 | fn store(objects: &Objects, dir: Dir) -> objects::Result<Id> { |
| 187 | let mut entries = dir.files; |
| 188 | for (name, sub) in dir.dirs { |
| 189 | entries.push(Entry { name, kind: Kind::Dir, id: store(objects, sub)? }); |
| 190 | } |
| 191 | objects.put_tree(&entries) |
| 192 | } |
| 193 | store(objects, root) |
| 194 | } |
| 195 | |
| 196 | /// Rebuild a stack of steps, made on `from`, onto `onto`. Returns the new snapshot of each |
| 197 | /// step, or the first step that conflicts and its paths. |
| 198 | pub fn rebuild(objects: &Objects, from: &Id, steps: &[Id], onto: &Id) -> objects::Result<Result<Vec<Id>, (usize, Vec<String>)>> { |
| 199 | let mut out = Vec::with_capacity(steps.len()); |
| 200 | let (mut prev, mut target) = (*from, *onto); |
| 201 | for (i, step) in steps.iter().enumerate() { |
| 202 | match merge_trees(objects, &prev, step, &target)? { |
| 203 | Outcome::Merged(id) => { |
| 204 | out.push(id); |
| 205 | prev = *step; |
| 206 | target = id; |
| 207 | } |
| 208 | Outcome::Conflicts(paths) => return Ok(Err((i, paths))), |
| 209 | } |
| 210 | } |
| 211 | Ok(Ok(out)) |
| 212 | } |
| 213 | |
| 214 | #[cfg(test)] |
| 215 | mod tests { |
| 216 | use super::*; |
| 217 | use crate::testdir::TestDir; |
| 218 | |
| 219 | #[test] |
| 220 | fn text() { |
| 221 | let base = "a\nb\nc\nd\ne\n"; |
| 222 | // Separate edits combine. |
| 223 | assert_eq!(merge_text(base, "A\nb\nc\nd\ne\n", "a\nb\nc\nd\nE\n"), Ok("A\nb\nc\nd\nE\n".into())); |
| 224 | // Insertions in different places. |
| 225 | assert_eq!(merge_text(base, "a\nx\nb\nc\nd\ne\n", "a\nb\nc\nd\ny\ne\n"), Ok("a\nx\nb\nc\nd\ny\ne\n".into())); |
| 226 | // The same edit on both sides is not a conflict. |
| 227 | assert_eq!(merge_text(base, "a\nB\nc\nd\ne\n", "a\nB\nc\nd\ne\n"), Ok("a\nB\nc\nd\ne\n".into())); |
| 228 | // Deletion on one side, an edit elsewhere on the other. |
| 229 | assert_eq!(merge_text(base, "a\nc\nd\ne\n", "a\nb\nc\nd\nE\n"), Ok("a\nc\nd\nE\n".into())); |
| 230 | // Different edits to the same line conflict. |
| 231 | assert_eq!(merge_text(base, "a\nX\nc\nd\ne\n", "a\nY\nc\nd\ne\n"), Err(1)); |
| 232 | // Trailing newline changes merge too. |
| 233 | assert_eq!(merge_text("a\nb\n", "a\nb", "A\nb\n"), Ok("A\nb".into())); |
| 234 | assert_eq!(merge_text("", "x\n", ""), Ok("x\n".into())); |
| 235 | } |
| 236 | |
| 237 | fn snap(objects: &Objects, files: &[(&str, &str)]) -> Id { |
| 238 | let map: Files = files.iter().map(|(p, c)| (p.to_string(), (Kind::File, objects.put_blob(c.as_bytes()).unwrap()))).collect(); |
| 239 | build_tree(objects, &map).unwrap() |
| 240 | } |
| 241 | |
| 242 | #[test] |
| 243 | fn trees() { |
| 244 | let dir = TestDir::new("merge-trees"); |
| 245 | let o = Objects::open(dir.path()).unwrap(); |
| 246 | let base = snap(&o, &[("a.txt", "1\n2\n3\n"), ("dir/b.txt", "b\n"), ("gone.txt", "x\n")]); |
| 247 | let ours = snap(&o, &[("a.txt", "one\n2\n3\n"), ("dir/b.txt", "b\n"), ("new.txt", "n\n")]); |
| 248 | let theirs = snap(&o, &[("a.txt", "1\n2\nthree\n"), ("dir/b.txt", "B\n"), ("gone.txt", "x\n")]); |
| 249 | let expected = snap(&o, &[("a.txt", "one\n2\nthree\n"), ("dir/b.txt", "B\n"), ("new.txt", "n\n")]); |
| 250 | assert_eq!(merge_trees(&o, &base, &ours, &theirs).unwrap(), Outcome::Merged(expected)); |
| 251 | |
| 252 | // Deleted on one side, edited on the other. |
| 253 | let edited = snap(&o, &[("a.txt", "1\n2\n3\n"), ("dir/b.txt", "b\n"), ("gone.txt", "changed\n")]); |
| 254 | assert_eq!(merge_trees(&o, &base, &ours, &edited).unwrap(), Outcome::Conflicts(vec!["gone.txt".into()])); |
| 255 | |
| 256 | // A file where the other side made a directory. |
| 257 | let as_file = snap(&o, &[("a.txt", "1\n2\n3\n"), ("dir/b.txt", "b\n"), ("gone.txt", "x\n"), ("x", "file\n")]); |
| 258 | let as_dir = snap(&o, &[("a.txt", "1\n2\n3\n"), ("dir/b.txt", "b\n"), ("gone.txt", "x\n"), ("x/inner", "in\n")]); |
| 259 | assert_eq!(merge_trees(&o, &base, &as_file, &as_dir).unwrap(), Outcome::Conflicts(vec!["x".into()])); |
| 260 | } |
| 261 | |
| 262 | #[test] |
| 263 | fn rebuilding_a_stack() { |
| 264 | let dir = TestDir::new("merge-rebuild"); |
| 265 | let o = Objects::open(dir.path()).unwrap(); |
| 266 | let base = snap(&o, &[("f", "1\n2\n3\n4\n5\n6\n")]); |
| 267 | let s1 = snap(&o, &[("f", "one\n2\n3\n4\n5\n6\n")]); |
| 268 | let s2 = snap(&o, &[("f", "one\n2\nthree\n4\n5\n6\n")]); |
| 269 | let main = snap(&o, &[("f", "1\n2\n3\n4\n5\nsix\n"), ("other", "x\n")]); |
| 270 | let rebuilt = rebuild(&o, &base, &[s1, s2], &main).unwrap().unwrap(); |
| 271 | assert_eq!(rebuilt[0], snap(&o, &[("f", "one\n2\n3\n4\n5\nsix\n"), ("other", "x\n")])); |
| 272 | assert_eq!(rebuilt[1], snap(&o, &[("f", "one\n2\nthree\n4\n5\nsix\n"), ("other", "x\n")])); |
| 273 | |
| 274 | // Main changed line 3 differently: the first step merges, the second conflicts. |
| 275 | let clash = snap(&o, &[("f", "1\n2\nTHREE\n4\n5\n6\n")]); |
| 276 | assert_eq!(rebuild(&o, &base, &[s1, s2], &clash).unwrap(), Err((1, vec!["f".into()]))); |
| 277 | } |
| 278 | } |