Onset: version control where nobody waits and nothing gets lost. The on command, its core and onset-server.
| 1 | //! Three-way merges: text line by line, JSON by key, and whole trees. |
| 2 | //! |
| 3 | //! The orientation is the same everywhere: `ours` is main and `theirs` is |
| 4 | //! the change being landed or synced. On the server ([`Mode::Land`]) any |
| 5 | //! conflict stops the landing. In a workspace ([`Mode::Sync`]) text conflicts |
| 6 | //! are written into the file with markers, and conflicts that can't be marked |
| 7 | //! (binary files, a file deleted on one side) keep the change's side and say |
| 8 | //! so. |
| 9 |
| 10 | use std::collections::BTreeMap; |
| 11 |
| 12 | use serde_json::Value; |
| 13 |
| 14 | use crate::{chunk, rename, smart}; |
| 15 | use crate::diff::{Hunk, hunks, is_binary, lines}; |
| 16 | use crate::object::{Kind, Object}; |
| 17 | use crate::tree::{self, EntryKind, TreeEntry}; |
| 18 | use crate::{Id, Layered, MemSource, Result, Source}; |
| 19 |
| 20 | /// The result of a text merge. |
| 21 | pub struct TextMerge { |
| 22 | pub content: Vec<u8>, |
| 23 | pub conflicts: usize, |
| 24 | } |
| 25 |
| 26 | /// Line-by-line three-way merge. Changes on both sides to the same or |
| 27 | /// touching lines are a conflict unless they're identical. |
| 28 | pub fn text(base: &[u8], ours: &[u8], theirs: &[u8], ours_label: &str, theirs_label: &str) -> TextMerge { |
| 29 | text_with(base, ours, theirs, ours_label, theirs_label, &|_, _, _, _| None, &|_| false) |
| 30 | } |
| 31 |
| 32 | /// Settles a spot both sides changed, from the base's lines there, each |
| 33 | /// side's text and the base's lines just before and after the spot: the |
| 34 | /// merged text, or None for a conflict. |
| 35 | type Resolve<'a> = &'a dyn Fn(&[&[u8]], &[u8], &[u8], (Option<&[u8]>, Option<&[u8]>)) -> Option<Vec<u8>>; |
| 36 |
| 37 | /// `force`: the change's hunks to show as conflicts even where main didn't |
| 38 | /// change those lines (see `mark_twice`). |
| 39 | fn text_with(base: &[u8], ours: &[u8], theirs: &[u8], ours_label: &str, theirs_label: &str, resolve: Resolve, force: &dyn Fn(&Hunk) -> bool) -> TextMerge { |
| 40 | let b = lines(base); |
| 41 | let o = lines(ours); |
| 42 | let t = lines(theirs); |
| 43 | let ho = hunks(base, ours); |
| 44 | let ht = hunks(base, theirs); |
| 45 | let mut out = Vec::with_capacity(ours.len().max(theirs.len())); |
| 46 | let mut conflicts = 0; |
| 47 | let (mut i, mut j) = (0, 0); |
| 48 | let mut pos: u32 = 0; |
| 49 | while i < ho.len() || j < ht.len() { |
| 50 | // Start a group at the earliest hunk. |
| 51 | let take_ours = j >= ht.len() || (i < ho.len() && ho[i].before.start <= ht[j].before.start); |
| 52 | let first = if take_ours { &ho[i] } else { &ht[j] }; |
| 53 | let lo = first.before.start; |
| 54 | let mut hi = first.before.end; |
| 55 | let (gi, gj) = (i, j); |
| 56 | if take_ours { |
| 57 | i += 1; |
| 58 | } else { |
| 59 | j += 1; |
| 60 | } |
| 61 | // Absorb every hunk that overlaps or touches the group. |
| 62 | loop { |
| 63 | if i < ho.len() && ho[i].before.start <= hi { |
| 64 | hi = hi.max(ho[i].before.end); |
| 65 | i += 1; |
| 66 | } else if j < ht.len() && ht[j].before.start <= hi { |
| 67 | hi = hi.max(ht[j].before.end); |
| 68 | j += 1; |
| 69 | } else { |
| 70 | break; |
| 71 | } |
| 72 | } |
| 73 | for line in &b[pos as usize..lo as usize] { |
| 74 | out.extend_from_slice(line); |
| 75 | } |
| 76 | let ours_hunks = &ho[gi..i]; |
| 77 | let theirs_hunks = &ht[gj..j]; |
| 78 | let side = |hs: &[Hunk], other: &[&[u8]]| -> Vec<u8> { |
| 79 | let mut text = Vec::new(); |
| 80 | let mut p = lo; |
| 81 | for h in hs { |
| 82 | for line in &b[p as usize..h.before.start as usize] { |
| 83 | text.extend_from_slice(line); |
| 84 | } |
| 85 | for line in &other[h.after.start as usize..h.after.end as usize] { |
| 86 | text.extend_from_slice(line); |
| 87 | } |
| 88 | p = h.before.end; |
| 89 | } |
| 90 | for line in &b[p as usize..hi as usize] { |
| 91 | text.extend_from_slice(line); |
| 92 | } |
| 93 | text |
| 94 | }; |
| 95 | let forced = theirs_hunks.iter().any(force); |
| 96 | if theirs_hunks.is_empty() { |
| 97 | out.extend_from_slice(&side(ours_hunks, &o)); |
| 98 | } else if ours_hunks.is_empty() && !forced { |
| 99 | out.extend_from_slice(&side(theirs_hunks, &t)); |
| 100 | } else { |
| 101 | let a = side(ours_hunks, &o); |
| 102 | let c = side(theirs_hunks, &t); |
| 103 | if a == c { |
| 104 | out.extend_from_slice(&a); |
| 105 | } else if let Some(merged) = (!forced) |
| 106 | .then(|| resolve(&b[lo as usize..hi as usize], &a, &c, ((lo > 0).then(|| b[lo as usize - 1]), b.get(hi as usize).copied()))) |
| 107 | .flatten() |
| 108 | { |
| 109 | out.extend_from_slice(&merged); |
| 110 | } else { |
| 111 | conflicts += 1; |
| 112 | if !out.is_empty() && !out.ends_with(b"\n") { |
| 113 | out.push(b'\n'); |
| 114 | } |
| 115 | out.extend_from_slice(format!("<<<<<<< {ours_label}\n").as_bytes()); |
| 116 | out.extend_from_slice(&a); |
| 117 | if !a.is_empty() && !a.ends_with(b"\n") { |
| 118 | out.push(b'\n'); |
| 119 | } |
| 120 | out.extend_from_slice(b"=======\n"); |
| 121 | out.extend_from_slice(&c); |
| 122 | if !c.is_empty() && !c.ends_with(b"\n") { |
| 123 | out.push(b'\n'); |
| 124 | } |
| 125 | out.extend_from_slice(format!(">>>>>>> {theirs_label}\n").as_bytes()); |
| 126 | } |
| 127 | } |
| 128 | pos = hi; |
| 129 | } |
| 130 | for line in &b[pos as usize..] { |
| 131 | out.extend_from_slice(line); |
| 132 | } |
| 133 | TextMerge { content: out, conflicts } |
| 134 | } |
| 135 |
| 136 | /// Merges JSON objects key by key. None when the files aren't all JSON |
| 137 | /// objects or both sides changed the same key differently. |
| 138 | pub fn json(base: Option<&[u8]>, ours: &[u8], theirs: &[u8]) -> Option<Vec<u8>> { |
| 139 | let parse = |b: &[u8]| serde_json::from_slice::<Value>(b).ok(); |
| 140 | let o = parse(ours)?; |
| 141 | let t = parse(theirs)?; |
| 142 | let b = match base { |
| 143 | Some(b) => parse(b)?, |
| 144 | None => Value::Object(Default::default()), |
| 145 | }; |
| 146 | if !(o.is_object() && t.is_object() && b.is_object()) { |
| 147 | return None; |
| 148 | } |
| 149 | let merged = json_value(Some(&b), Some(&o), Some(&t))??; |
| 150 | // Write it back in ours' style. |
| 151 | let text = String::from_utf8_lossy(ours); |
| 152 | let indent = text |
| 153 | .lines() |
| 154 | .skip(1) |
| 155 | .find(|l| l.starts_with([' ', '\t'])) |
| 156 | .map(|l| l.chars().take_while(|c| *c == ' ' || *c == '\t').collect::<String>()) |
| 157 | .unwrap_or_else(|| " ".into()); |
| 158 | let mut out = Vec::new(); |
| 159 | let formatter = serde_json::ser::PrettyFormatter::with_indent(indent.as_bytes()); |
| 160 | let mut ser = serde_json::Serializer::with_formatter(&mut out, formatter); |
| 161 | serde::Serialize::serialize(&merged, &mut ser).ok()?; |
| 162 | if ours.ends_with(b"\n") { |
| 163 | out.push(b'\n'); |
| 164 | } |
| 165 | Some(out) |
| 166 | } |
| 167 |
| 168 | /// Some(None): the key is gone. None: a conflict. |
| 169 | fn json_value(b: Option<&Value>, o: Option<&Value>, t: Option<&Value>) -> Option<Option<Value>> { |
| 170 | if o == t { |
| 171 | return Some(o.cloned()); |
| 172 | } |
| 173 | if b == o { |
| 174 | return Some(t.cloned()); |
| 175 | } |
| 176 | if b == t { |
| 177 | return Some(o.cloned()); |
| 178 | } |
| 179 | let (Some(Value::Object(om)), Some(Value::Object(tm))) = (o, t) else { return None }; |
| 180 | let empty = serde_json::Map::new(); |
| 181 | let bm = match b { |
| 182 | Some(Value::Object(m)) => m, |
| 183 | None => &empty, |
| 184 | _ => return None, |
| 185 | }; |
| 186 | let mut out = serde_json::Map::new(); |
| 187 | for (k, ov) in om { |
| 188 | if let Some(v) = json_value(bm.get(k), Some(ov), tm.get(k))? { |
| 189 | out.insert(k.clone(), v); |
| 190 | } |
| 191 | } |
| 192 | // Keys only theirs has, placed after the key they follow in theirs. |
| 193 | let keys: Vec<&String> = tm.keys().collect(); |
| 194 | for (idx, k) in keys.iter().enumerate() { |
| 195 | if om.contains_key(*k) || bm.contains_key(*k) { |
| 196 | if !om.contains_key(*k) { |
| 197 | // Deleted on ours: handled above only for keys ours has. |
| 198 | if let Some(v) = json_value(bm.get(*k), None, tm.get(*k))? { |
| 199 | out.insert((*k).clone(), v); |
| 200 | } |
| 201 | } |
| 202 | continue; |
| 203 | } |
| 204 | let value = tm[*k].clone(); |
| 205 | let after = keys[..idx].iter().rev().find(|p| out.contains_key(**p)).map(|p| (*p).clone()); |
| 206 | insert_after(&mut out, after.as_deref(), (*k).clone(), value); |
| 207 | } |
| 208 | Some(Some(Value::Object(out))) |
| 209 | } |
| 210 |
| 211 | fn insert_after(map: &mut serde_json::Map<String, Value>, after: Option<&str>, key: String, value: Value) { |
| 212 | let Some(after) = after else { |
| 213 | // Theirs put it first. |
| 214 | let rest = std::mem::take(map); |
| 215 | map.insert(key, value); |
| 216 | map.extend(rest); |
| 217 | return; |
| 218 | }; |
| 219 | let rest: Vec<(String, Value)> = std::mem::take(map).into_iter().collect(); |
| 220 | for (k, v) in rest { |
| 221 | let hit = k == after; |
| 222 | map.insert(k, v); |
| 223 | if hit { |
| 224 | map.insert(key.clone(), value.clone()); |
| 225 | } |
| 226 | } |
| 227 | } |
| 228 |
| 229 | #[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 230 | pub enum Mode { |
| 231 | /// Landing on the server: any conflict stops it. |
| 232 | Land, |
| 233 | /// Syncing a workspace: conflicts are written into files. |
| 234 | Sync, |
| 235 | } |
| 236 |
| 237 | /// A conflict the merge found. |
| 238 | #[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)] |
| 239 | pub struct Conflict { |
| 240 | pub path: String, |
| 241 | /// text, binary, deleted, type, or duplicate (both sides declare one thing). |
| 242 | pub kind: String, |
| 243 | /// What a duplicate is ("both sides declare helper"). |
| 244 | #[serde(default, skip_serializing_if = "Option::is_none")] |
| 245 | pub detail: Option<String>, |
| 246 | } |
| 247 |
| 248 | /// Something sync resolved on its own that the person should know about. |
| 249 | #[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)] |
| 250 | pub struct Note { |
| 251 | pub path: String, |
| 252 | pub message: String, |
| 253 | } |
| 254 |
| 255 | pub struct TreeMerge { |
| 256 | pub tree: Id, |
| 257 | /// Objects the merge created (merged blobs and trees). |
| 258 | pub objects: MemSource, |
| 259 | pub conflicts: Vec<Conflict>, |
| 260 | pub notes: Vec<Note>, |
| 261 | } |
| 262 |
| 263 | impl TreeMerge { |
| 264 | pub fn clean(&self) -> bool { |
| 265 | self.conflicts.is_empty() |
| 266 | } |
| 267 | } |
| 268 |
| 269 | /// Merges trees: `base` is where the change started, `ours` is main and |
| 270 | /// `theirs` is the change. |
| 271 | pub fn trees(src: &dyn Source, base: Option<&Id>, ours: &Id, theirs: &Id, mode: Mode, labels: (&str, &str)) -> Result<TreeMerge> { |
| 272 | merge_trees(src, base, ours, theirs, mode, labels, false) |
| 273 | } |
| 274 |
| 275 | /// `trees`, or (`general`, for tests) without its shortcuts. |
| 276 | fn merge_trees(src: &dyn Source, base: Option<&Id>, ours: &Id, theirs: &Id, mode: Mode, labels: (&str, &str), general: bool) -> Result<TreeMerge> { |
| 277 | let mut m = Merger { src, mode, labels, objects: MemSource::default(), conflicts: Vec::new(), notes: Vec::new(), general }; |
| 278 | let empty = tree::empty_id(); |
| 279 | m.objects.put(tree::empty()); |
| 280 | let base = base.copied().unwrap_or(empty); |
| 281 | // A file one side moved and the other edited: the edit moves with it. |
| 282 | let (base, ours, theirs) = m.follow_renames(&base, ours, theirs)?; |
| 283 | let tree = m.merge_tree(&base, &ours, &theirs, "")?; |
| 284 | Ok(TreeMerge { tree, objects: m.objects, conflicts: m.conflicts, notes: m.notes }) |
| 285 | } |
| 286 |
| 287 | struct Merger<'a> { |
| 288 | src: &'a dyn Source, |
| 289 | mode: Mode, |
| 290 | labels: (&'a str, &'a str), |
| 291 | objects: MemSource, |
| 292 | conflicts: Vec<Conflict>, |
| 293 | notes: Vec<Note>, |
| 294 | /// Without the shortcuts (tests check they change nothing). |
| 295 | general: bool, |
| 296 | } |
| 297 |
| 298 | impl Merger<'_> { |
| 299 | fn read(&self, id: &Id) -> Result<Vec<TreeEntry>> { |
| 300 | let src = Layered { first: &self.objects, second: self.src }; |
| 301 | tree::read(&src, id) |
| 302 | } |
| 303 |
| 304 | fn file(&self, id: &Id) -> Result<Object> { |
| 305 | let src = Layered { first: &self.objects, second: self.src }; |
| 306 | src.must(id) |
| 307 | } |
| 308 |
| 309 | /// Where one side moved a file the other side edited (and didn't move), |
| 310 | /// the edited side and the base get the file at its new name too, so the |
| 311 | /// edit merges there instead of conflicting with a delete. |
| 312 | fn follow_renames(&mut self, base: &Id, ours: &Id, theirs: &Id) -> Result<(Id, Id, Id)> { |
| 313 | if base == ours || base == theirs || ours == theirs { |
| 314 | return Ok((*base, *ours, *theirs)); |
| 315 | } |
| 316 | let (mut b, mut o, mut t) = (*base, *ours, *theirs); |
| 317 | let src = Layered { first: &self.objects, second: self.src }; |
| 318 | let theirs_changes = tree::diff_trees(&src, base, theirs)?; |
| 319 | // A move needs a file gone from one side: with nothing gone from the |
| 320 | // change, and every file it edits still a file on main, there's none |
| 321 | // to follow, and main's changes (often many more) needn't be listed. |
| 322 | let mut gone = theirs_changes.values().any(|c| matches!(c, tree::Change::Removed(_))); |
| 323 | for (path, change) in &theirs_changes { |
| 324 | if gone { |
| 325 | break; |
| 326 | } |
| 327 | if matches!(change, tree::Change::Modified(..)) { |
| 328 | gone = !tree::lookup(&src, ours, path)?.is_some_and(|e| e.kind != EntryKind::Tree); |
| 329 | } |
| 330 | } |
| 331 | if !gone && !self.general { |
| 332 | return Ok((b, o, t)); |
| 333 | } |
| 334 | let ours_changes = tree::diff_trees(&src, base, ours)?; |
| 335 | let mut moves: Vec<(bool, String, String, tree::Entry, tree::Entry)> = Vec::new(); |
| 336 | for (theirs_moved, moved, edited) in [(true, &theirs_changes, &ours_changes), (false, &ours_changes, &theirs_changes)] { |
| 337 | for (from, to) in rename::renames(&src, moved)? { |
| 338 | if let Some(tree::Change::Modified(before, after)) = edited.get(&from) |
| 339 | && !edited.contains_key(&to) |
| 340 | { |
| 341 | moves.push((theirs_moved, from, to, *before, *after)); |
| 342 | } |
| 343 | } |
| 344 | } |
| 345 | for (theirs_moved, from, to, before, after) in moves { |
| 346 | let src = Layered { first: &self.objects, second: self.src }; |
| 347 | let (nb, made_b) = rename::moved(&src, &b, &from, &to, before)?; |
| 348 | let (ne, made_e) = rename::moved(&src, if theirs_moved { &o } else { &t }, &from, &to, after)?; |
| 349 | for obj in made_b.into_iter().chain(made_e) { |
| 350 | self.objects.put(obj); |
| 351 | } |
| 352 | b = nb; |
| 353 | if theirs_moved { |
| 354 | o = ne; |
| 355 | } else { |
| 356 | t = ne; |
| 357 | } |
| 358 | let who = if theirs_moved { "your change" } else { "main" }; |
| 359 | self.notes.push(Note { path: to.clone(), message: format!("{who} moved {from} to {to}; the other side's edits to it came along") }); |
| 360 | } |
| 361 | Ok((b, o, t)) |
| 362 | } |
| 363 |
| 364 | fn merge_tree(&mut self, base: &Id, ours: &Id, theirs: &Id, prefix: &str) -> Result<Id> { |
| 365 | if ours == theirs || base == theirs { |
| 366 | return Ok(*ours); |
| 367 | } |
| 368 | if base == ours { |
| 369 | return Ok(*theirs); |
| 370 | } |
| 371 | let (bo, oo, to) = (self.file(base)?, self.file(ours)?, self.file(theirs)?); |
| 372 | for (o, id) in [(&bo, base), (&oo, ours), (&to, theirs)] { |
| 373 | if o.kind != Kind::Tree { |
| 374 | return Err(crate::corrupt(format!("{} isn't a tree", id.short()))); |
| 375 | } |
| 376 | } |
| 377 | if !self.general |
| 378 | && let (Some(b), Some(o), Some(t)) = (tree::raw_entries(&bo.data)?, tree::raw_entries(&oo.data)?, tree::raw_entries(&to.data)?) |
| 379 | { |
| 380 | return self.merge_sorted(&b, &o, &t, prefix); |
| 381 | } |
| 382 | let map = |es: Vec<TreeEntry>| es.into_iter().map(|e| (e.name.clone(), e)).collect::<BTreeMap<_, _>>(); |
| 383 | let b = map(self.read(base)?); |
| 384 | let o = map(self.read(ours)?); |
| 385 | let t = map(self.read(theirs)?); |
| 386 | let mut names: Vec<&String> = b.keys().chain(o.keys()).chain(t.keys()).collect(); |
| 387 | names.sort(); |
| 388 | names.dedup(); |
| 389 | let mut out = Vec::new(); |
| 390 | for name in names { |
| 391 | let path = if prefix.is_empty() { name.clone() } else { format!("{prefix}/{name}") }; |
| 392 | if let Some(e) = self.merge_entry(b.get(name), o.get(name), t.get(name), &path)? { |
| 393 | out.push(TreeEntry { name: name.clone(), kind: e.0, id: e.1 }); |
| 394 | } |
| 395 | } |
| 396 | Ok(self.objects.put(Object::new(Kind::Tree, tree::encode(&out)))) |
| 397 | } |
| 398 |
| 399 | /// `merge_tree` on folders whose entries are in order (as written): one |
| 400 | /// pass over the three, names copied only where both sides changed one. |
| 401 | /// The same folder as the general path, written as `tree::encode` would. |
| 402 | fn merge_sorted(&mut self, b: &[tree::RawEntry<'_>], o: &[tree::RawEntry<'_>], t: &[tree::RawEntry<'_>], prefix: &str) -> Result<Id> { |
| 403 | let (mut i, mut j, mut k) = (0, 0, 0); |
| 404 | let mut out = Vec::with_capacity(o.len().max(t.len()) * 48); |
| 405 | loop { |
| 406 | let name = [b.get(i), o.get(j), t.get(k)].into_iter().flatten().map(|e| e.name).min_by(|x, y| x.as_bytes().cmp(y.as_bytes())); |
| 407 | let Some(name) = name else { break }; |
| 408 | let take = |es: &[tree::RawEntry<'_>], at: &mut usize| { |
| 409 | let e = es.get(*at).filter(|e| e.name == name).map(|e| (e.kind, e.id)); |
| 410 | if e.is_some() { |
| 411 | *at += 1; |
| 412 | } |
| 413 | e |
| 414 | }; |
| 415 | let (kb, ko, kt) = (take(b, &mut i), take(o, &mut j), take(t, &mut k)); |
| 416 | let merged = if ko == kt || kb == kt { |
| 417 | ko |
| 418 | } else if kb == ko { |
| 419 | kt |
| 420 | } else { |
| 421 | let entry = |e: Option<(EntryKind, Id)>| e.map(|(kind, id)| TreeEntry { name: name.to_string(), kind, id }); |
| 422 | let path = if prefix.is_empty() { name.to_string() } else { format!("{prefix}/{name}") }; |
| 423 | self.merge_entry(entry(kb).as_ref(), entry(ko).as_ref(), entry(kt).as_ref(), &path)? |
| 424 | }; |
| 425 | if let Some((kind, id)) = merged { |
| 426 | out.push(kind as u8); |
| 427 | out.extend_from_slice(&(name.len() as u16).to_le_bytes()); |
| 428 | out.extend_from_slice(name.as_bytes()); |
| 429 | out.extend_from_slice(&id.0); |
| 430 | } |
| 431 | } |
| 432 | Ok(self.objects.put(Object::new(Kind::Tree, out))) |
| 433 | } |
| 434 |
| 435 | fn merge_entry(&mut self, b: Option<&TreeEntry>, o: Option<&TreeEntry>, t: Option<&TreeEntry>, path: &str) -> Result<Option<(EntryKind, Id)>> { |
| 436 | let key = |e: Option<&TreeEntry>| e.map(|e| (e.kind, e.id)); |
| 437 | let (kb, ko, kt) = (key(b), key(o), key(t)); |
| 438 | if ko == kt || kb == kt { |
| 439 | return Ok(ko); |
| 440 | } |
| 441 | if kb == ko { |
| 442 | return Ok(kt); |
| 443 | } |
| 444 | let is_tree = |e: Option<&TreeEntry>| e.is_some_and(|e| e.kind == EntryKind::Tree); |
| 445 | let is_file = |e: Option<&TreeEntry>| e.is_some_and(|e| e.kind != EntryKind::Tree); |
| 446 | match (o, t) { |
| 447 | (Some(oe), Some(te)) if is_tree(o) && is_tree(t) => { |
| 448 | let base = if is_tree(b) { b.unwrap().id } else { tree::empty_id() }; |
| 449 | Ok(Some((EntryKind::Tree, self.merge_tree(&base, &oe.id, &te.id, path)?))) |
| 450 | } |
| 451 | (Some(oe), Some(te)) if is_file(o) && is_file(t) => self.merge_file(b.filter(|e| e.kind != EntryKind::Tree), oe, te, path), |
| 452 | (None, Some(te)) => { |
| 453 | // Main deleted what the change edited. |
| 454 | self.unmarkable(path, "deleted", Some(te), format!("main deleted {path}; kept your version")) |
| 455 | } |
| 456 | (Some(_), None) => { |
| 457 | // The change deleted what main edited. |
| 458 | self.unmarkable(path, "deleted", None, format!("you deleted {path}, which main also changed; `on restore {path} --from main` brings main's back")) |
| 459 | } |
| 460 | _ => { |
| 461 | // A file on one side, a folder on the other. |
| 462 | self.unmarkable(path, "type", t, format!("{path} is a file on one side and a folder on the other; kept yours")) |
| 463 | } |
| 464 | } |
| 465 | } |
| 466 |
| 467 | /// A conflict that can't be written with markers: landing stops; sync |
| 468 | /// keeps the change's side (`keep`) and says so. |
| 469 | fn unmarkable(&mut self, path: &str, kind: &'static str, keep: Option<&TreeEntry>, note: String) -> Result<Option<(EntryKind, Id)>> { |
| 470 | self.conflicts.push(Conflict { path: path.to_string(), kind: kind.to_string(), detail: None }); |
| 471 | if self.mode == Mode::Sync { |
| 472 | self.conflicts.pop(); |
| 473 | self.notes.push(Note { path: path.to_string(), message: note }); |
| 474 | } |
| 475 | Ok(keep.map(|e| (e.kind, e.id))) |
| 476 | } |
| 477 |
| 478 | fn merge_file(&mut self, b: Option<&TreeEntry>, o: &TreeEntry, t: &TreeEntry, path: &str) -> Result<Option<(EntryKind, Id)>> { |
| 479 | // The kind (exec bit, link) merges on its own. |
| 480 | let kind = if o.kind == t.kind { |
| 481 | o.kind |
| 482 | } else if b.is_some_and(|b| b.kind == o.kind) { |
| 483 | t.kind |
| 484 | } else if b.is_some_and(|b| b.kind == t.kind) { |
| 485 | o.kind |
| 486 | } else { |
| 487 | t.kind |
| 488 | }; |
| 489 | if o.id == t.id { |
| 490 | return Ok(Some((kind, o.id))); |
| 491 | } |
| 492 | if b.is_some_and(|b| b.id == o.id) { |
| 493 | return Ok(Some((kind, t.id))); |
| 494 | } |
| 495 | if b.is_some_and(|b| b.id == t.id) { |
| 496 | return Ok(Some((kind, o.id))); |
| 497 | } |
| 498 | let oo = self.file(&o.id)?; |
| 499 | let to = self.file(&t.id)?; |
| 500 | let bo = match b { |
| 501 | Some(b) => Some(self.file(&b.id)?), |
| 502 | None => None, |
| 503 | }; |
| 504 | let text = |obj: &Object| obj.kind == Kind::Blob && !is_binary(&obj.data); |
| 505 | let all_text = text(&oo) && text(&to) && bo.as_ref().is_none_or(text) && o.kind != EntryKind::Link && t.kind != EntryKind::Link && o.kind != EntryKind::Gitlink && t.kind != EntryKind::Gitlink; |
| 506 | if !all_text { |
| 507 | return self.unmarkable(path, "binary", Some(t), format!("{path} changed on main and in your change and can't be merged line by line; kept yours, `on restore {path} --from main` takes main's")); |
| 508 | } |
| 509 | let base_bytes: &[u8] = bo.as_ref().map(|b| b.data.as_slice()).unwrap_or(b""); |
| 510 | // Two new files at one path stay a conflict, as in git; smart merges are for files that were there. |
| 511 | let merged = if bo.is_some() { text_for(path, base_bytes, &oo.data, &to.data, self.labels.0, self.labels.1) } else { crate::merge::text(base_bytes, &oo.data, &to.data, self.labels.0, self.labels.1) }; |
| 512 | // A merge that declares something twice that neither side did alone |
| 513 | // (two `def helper`, `timeout:` twice in one map) isn't clean, even |
| 514 | // where the lines didn't touch. |
| 515 | let twice = if merged.conflicts == 0 { suspect(path, &oo.data, &to.data, &merged.content) } else { Vec::new() }; |
| 516 | if merged.conflicts == 0 && twice.is_empty() { |
| 517 | let id = self.put_file(merged.content); |
| 518 | return Ok(Some((kind, id))); |
| 519 | } |
| 520 | if path.ends_with(".json") |
| 521 | && let Some(content) = json(bo.as_ref().map(|b| b.data.as_slice()), &oo.data, &to.data) |
| 522 | { |
| 523 | let id = self.put_file(content); |
| 524 | return Ok(Some((kind, id))); |
| 525 | } |
| 526 | if path.ends_with(".toml") |
| 527 | && let Some(content) = smart::toml(bo.as_ref().map(|b| b.data.as_slice()), &oo.data, &to.data) |
| 528 | && suspect(path, &oo.data, &to.data, &content).is_empty() |
| 529 | { |
| 530 | let id = self.put_file(content); |
| 531 | return Ok(Some((kind, id))); |
| 532 | } |
| 533 | let detail = (!twice.is_empty()).then(|| format!("both sides declare {}", twice.iter().map(|k| crate::decls::short(k)).collect::<Vec<_>>().join(", "))); |
| 534 | self.conflicts.push(Conflict { path: path.to_string(), kind: if twice.is_empty() { "text" } else { "duplicate" }.into(), detail: detail.clone() }); |
| 535 | match self.mode { |
| 536 | Mode::Land => Ok(Some((kind, t.id))), |
| 537 | Mode::Sync => { |
| 538 | let content = if twice.is_empty() { merged.content } else { mark_twice(path, base_bytes, &oo.data, &to.data, self.labels, &twice) }; |
| 539 | if let Some(d) = detail { |
| 540 | self.notes.push(Note { path: path.to_string(), message: format!("{path}: {d}; keep one, then land") }); |
| 541 | } |
| 542 | let id = self.put_file(content); |
| 543 | Ok(Some((kind, id))) |
| 544 | } |
| 545 | } |
| 546 | } |
| 547 |
| 548 | fn put_file(&mut self, content: Vec<u8>) -> Id { |
| 549 | let objects = chunk::file_objects(&content); |
| 550 | let id = objects[0].id(); |
| 551 | for o in objects { |
| 552 | self.objects.put(o); |
| 553 | } |
| 554 | id |
| 555 | } |
| 556 | } |
| 557 |
| 558 | /// A text merge for the file at `path`, settling what smart merges can (see `smart`). |
| 559 | pub fn text_for(path: &str, base: &[u8], ours: &[u8], theirs: &[u8], ol: &str, tl: &str) -> TextMerge { |
| 560 | text_with(base, ours, theirs, ol, tl, &smart::resolver(path), &|_| false) |
| 561 | } |
| 562 |
| 563 | /// What a clean-looking merge of `path` declares twice that neither side did |
| 564 | /// alone, and JSON that doesn't parse where both sides did. |
| 565 | pub fn suspect(path: &str, ours: &[u8], theirs: &[u8], merged: &[u8]) -> Vec<String> { |
| 566 | let mut out = crate::decls::new_duplicates(path, ours, theirs, merged); |
| 567 | if path.ends_with(".json") { |
| 568 | let parses = |b: &[u8]| serde_json::from_slice::<Value>(b).is_ok(); |
| 569 | if parses(ours) && parses(theirs) && !parses(merged) { |
| 570 | out.push("valid JSON".into()); |
| 571 | } |
| 572 | } |
| 573 | out |
| 574 | } |
| 575 |
| 576 | /// The merge with each spot where the change added a second one of `twice` |
| 577 | /// marked as a conflict (main's side empty), so sync can show it. If none can |
| 578 | /// be placed, the whole file is the conflict. |
| 579 | fn mark_twice(path: &str, base: &[u8], ours: &[u8], theirs: &[u8], labels: (&str, &str), twice: &[String]) -> Vec<u8> { |
| 580 | let mut lines: Vec<usize> = twice.iter().flat_map(|k| crate::decls::lines_of(path, theirs, k)).collect(); |
| 581 | lines.sort_unstable(); |
| 582 | let force = |h: &Hunk| lines.iter().any(|&l| (h.after.start as usize..h.after.end as usize).contains(&l)); |
| 583 | let marked = text_with(base, ours, theirs, labels.0, labels.1, &smart::resolver(path), &force); |
| 584 | if marked.conflicts > 0 { |
| 585 | return marked.content; |
| 586 | } |
| 587 | let mut out = format!("<<<<<<< {}\n", labels.0).into_bytes(); |
| 588 | out.extend_from_slice(ours); |
| 589 | if !ours.ends_with(b"\n") { |
| 590 | out.push(b'\n'); |
| 591 | } |
| 592 | out.extend_from_slice(b"=======\n"); |
| 593 | out.extend_from_slice(theirs); |
| 594 | if !theirs.ends_with(b"\n") { |
| 595 | out.push(b'\n'); |
| 596 | } |
| 597 | out.extend_from_slice(format!(">>>>>>> {}\n", labels.1).as_bytes()); |
| 598 | out |
| 599 | } |
| 600 |
| 601 | #[cfg(test)] |
| 602 | mod tests { |
| 603 | use super::*; |
| 604 | use crate::tree::{Entry, Files, build, flatten}; |
| 605 |
| 606 | #[test] |
| 607 | fn clean_text_merge() { |
| 608 | let base = b"a\nb\nc\nd\ne\nf\n"; |
| 609 | let ours = b"A\nb\nc\nd\ne\nf\n"; |
| 610 | let theirs = b"a\nb\nc\nd\ne\nF\n"; |
| 611 | let m = text(base, ours, theirs, "main", "change"); |
| 612 | assert_eq!(m.conflicts, 0); |
| 613 | assert_eq!(m.content, b"A\nb\nc\nd\ne\nF\n"); |
| 614 | } |
| 615 |
| 616 | #[test] |
| 617 | fn conflicting_text_merge() { |
| 618 | let base = b"a\nb\nc\n"; |
| 619 | let ours = b"a\nB1\nc\n"; |
| 620 | let theirs = b"a\nB2\nc\n"; |
| 621 | let m = text(base, ours, theirs, "main 4", "your change bcdf"); |
| 622 | assert_eq!(m.conflicts, 1); |
| 623 | assert_eq!(String::from_utf8(m.content).unwrap(), "a\n<<<<<<< main 4\nB1\n=======\nB2\n>>>>>>> your change bcdf\nc\n"); |
| 624 | } |
| 625 |
| 626 | #[test] |
| 627 | fn same_change_both_sides() { |
| 628 | let m = text(b"a\nb\n", b"a\nX\n", b"a\nX\n", "o", "t"); |
| 629 | assert_eq!(m.conflicts, 0); |
| 630 | assert_eq!(m.content, b"a\nX\n"); |
| 631 | } |
| 632 |
| 633 | #[test] |
| 634 | fn json_keys_merge() { |
| 635 | let base = b"{\n \"a\": \"1\"\n}\n"; |
| 636 | let ours = b"{\n \"a\": \"1\",\n \"b\": \"2\"\n}\n"; |
| 637 | let theirs = b"{\n \"a\": \"1\",\n \"c\": \"3\"\n}\n"; |
| 638 | // Line by line this is a conflict (both added after "a"). |
| 639 | assert_eq!(text(base, ours, theirs, "o", "t").conflicts, 1); |
| 640 | let merged = json(Some(base), ours, theirs).unwrap(); |
| 641 | let v: Value = serde_json::from_slice(&merged).unwrap(); |
| 642 | assert_eq!(v["b"], "2"); |
| 643 | assert_eq!(v["c"], "3"); |
| 644 | assert!(json(Some(base), b"{\"a\": \"x\"}", b"{\"a\": \"y\"}").is_none()); |
| 645 | } |
| 646 |
| 647 | fn put_files(src: &mut MemSource, list: &[(&str, &str)]) -> Id { |
| 648 | let files: Files = list |
| 649 | .iter() |
| 650 | .map(|(p, c)| (p.to_string(), Entry { kind: EntryKind::File, id: src.put(Object::blob(c.as_bytes().to_vec())) })) |
| 651 | .collect(); |
| 652 | let (root, trees) = build(&files); |
| 653 | for t in trees { |
| 654 | src.put(t); |
| 655 | } |
| 656 | root |
| 657 | } |
| 658 |
| 659 | #[test] |
| 660 | fn tree_merges() { |
| 661 | let mut src = MemSource::default(); |
| 662 | let base = put_files(&mut src, &[("a.txt", "a\nb\nc\n"), ("src/x.rs", "x\n"), ("keys.json", "{\n \"a\": 1\n}\n")]); |
| 663 | let ours = put_files(&mut src, &[("a.txt", "A\nb\nc\n"), ("src/x.rs", "x\n"), ("src/new.rs", "n\n"), ("keys.json", "{\n \"a\": 1,\n \"b\": 2\n}\n")]); |
| 664 | let theirs = put_files(&mut src, &[("a.txt", "a\nb\nC\n"), ("src/x.rs", "x2\n"), ("keys.json", "{\n \"a\": 1,\n \"c\": 3\n}\n")]); |
| 665 | let m = trees(&src, Some(&base), &ours, &theirs, Mode::Land, ("main", "change")).unwrap(); |
| 666 | assert!(m.clean(), "{:?}", m.conflicts); |
| 667 | let layered = Layered { first: &m.objects, second: &src }; |
| 668 | let files = flatten(&layered, &m.tree).unwrap(); |
| 669 | let read = |p: &str| String::from_utf8(layered.must(&files[p].id).unwrap().data).unwrap(); |
| 670 | assert_eq!(read("a.txt"), "A\nb\nC\n"); |
| 671 | assert_eq!(read("src/x.rs"), "x2\n"); |
| 672 | assert_eq!(read("src/new.rs"), "n\n"); |
| 673 | let keys: Value = serde_json::from_str(&read("keys.json")).unwrap(); |
| 674 | assert_eq!((keys["b"].as_i64(), keys["c"].as_i64()), (Some(2), Some(3))); |
| 675 | } |
| 676 |
| 677 | /// Merges one file three ways through `trees`: its conflicts' kinds, and the file sync writes. |
| 678 | fn merge_one(path: &str, base: &str, ours: &str, theirs: &str) -> (Vec<String>, String) { |
| 679 | let mut src = MemSource::default(); |
| 680 | let b = put_files(&mut src, &[(path, base)]); |
| 681 | let o = put_files(&mut src, &[(path, ours)]); |
| 682 | let t = put_files(&mut src, &[(path, theirs)]); |
| 683 | let land = trees(&src, Some(&b), &o, &t, Mode::Land, ("main", "change")).unwrap(); |
| 684 | let sync = trees(&src, Some(&b), &o, &t, Mode::Sync, ("main", "change")).unwrap(); |
| 685 | assert_eq!(land.conflicts.len(), sync.conflicts.len(), "land and sync agree"); |
| 686 | let layered = Layered { first: &sync.objects, second: &src }; |
| 687 | let files = flatten(&layered, &sync.tree).unwrap(); |
| 688 | let text = String::from_utf8(layered.must(&files[path].id).unwrap().data).unwrap(); |
| 689 | (land.conflicts.iter().map(|c| c.kind.clone()).collect(), text) |
| 690 | } |
| 691 |
| 692 | #[test] |
| 693 | fn never_two_of_one_thing() { |
| 694 | // Two new functions at the end of a file both go in (git: a conflict). |
| 695 | let base = "export function one() {\n return 1;\n}\n"; |
| 696 | let (kinds, text) = merge_one( |
| 697 | "app.js", |
| 698 | base, |
| 699 | &format!("{base}\nexport function two() {{\n return 2;\n}}\n"), |
| 700 | &format!("{base}\nexport function three() {{\n return 3;\n}}\n"), |
| 701 | ); |
| 702 | assert!(kinds.is_empty(), "{kinds:?}"); |
| 703 | assert!(text.contains("function two") && text.contains("function three")); |
| 704 | // Two different `def helper` in one module: a conflict, never both. |
| 705 | let base = "def base():\n return 0\n"; |
| 706 | let (kinds, text) = merge_one( |
| 707 | "util.py", |
| 708 | base, |
| 709 | &format!("{base}\ndef helper(x):\n return x + 1\n"), |
| 710 | &format!("{base}\ndef helper(items):\n return len(items)\n"), |
| 711 | ); |
| 712 | assert_eq!(kinds.len(), 1); |
| 713 | assert!(text.contains("<<<<<<< main")); |
| 714 | // The same key twice in one YAML map: a conflict. |
| 715 | let (kinds, _) = merge_one("config.yaml", "server:\n port: 80\n", "server:\n port: 80\n timeout: 30\n", "server:\n port: 80\n timeout: 5\n"); |
| 716 | assert_eq!(kinds.len(), 1); |
| 717 | // Git merges these cleanly (the lines don't touch), but the module ends up with two `total`. |
| 718 | let base = "def a():\n return 1\n\n\ndef b():\n return 2\n"; |
| 719 | let (kinds, text) = merge_one( |
| 720 | "shop.py", |
| 721 | base, |
| 722 | &format!("def total():\n return 0\n\n\n{base}"), |
| 723 | &format!("{base}\n\n\ndef total():\n return 9\n"), |
| 724 | ); |
| 725 | assert_eq!(kinds, vec!["duplicate"]); |
| 726 | assert_eq!(text.matches("<<<<<<<").count(), 1); |
| 727 | assert!(text.contains("def total():\n return 0"), "main's stays where it was"); |
| 728 | // Statements added at one spot keep git's conflict: their order matters. |
| 729 | let base = "function run() {\n start();\n}\n"; |
| 730 | let (kinds, _) = merge_one("run.js", base, "function run() {\n start();\n save();\n}\n", "function run() {\n start();\n send();\n}\n"); |
| 731 | assert_eq!(kinds, vec!["text"]); |
| 732 | // Two imports binding one name don't merge into two. |
| 733 | let (kinds, _) = merge_one( |
| 734 | "app.ts", |
| 735 | "import { a } from \"x\";\n\nrun();\n", |
| 736 | "import { a, b } from \"x\";\n\nrun();\n", |
| 737 | "import { a, c } from \"x\";\n\nrun();\n", |
| 738 | ); |
| 739 | assert_eq!(kinds.len(), 1); |
| 740 | // Two scripts with one name in package.json: a conflict, not a silent last-one-wins. |
| 741 | let base = "{\n \"scripts\": {\n \"build\": \"x\"\n }\n}\n"; |
| 742 | let (kinds, _) = merge_one( |
| 743 | "package.json", |
| 744 | base, |
| 745 | "{\n \"scripts\": {\n \"build\": \"x\",\n \"test\": \"jest\"\n }\n}\n", |
| 746 | "{\n \"scripts\": {\n \"build\": \"x\",\n \"test\": \"vitest\"\n }\n}\n", |
| 747 | ); |
| 748 | assert_eq!(kinds.len(), 1); |
| 749 | // Two new tests at one spot both go in. |
| 750 | let base = "describe(\"cart\", () => {\n it(\"adds\", () => {\n add();\n });\n});\n"; |
| 751 | let (kinds, text) = merge_one( |
| 752 | "cart.test.ts", |
| 753 | base, |
| 754 | "describe(\"cart\", () => {\n it(\"adds\", () => {\n add();\n });\n it(\"removes\", () => {\n remove();\n });\n});\n", |
| 755 | "describe(\"cart\", () => {\n it(\"adds\", () => {\n add();\n });\n it(\"empties\", () => {\n empty();\n });\n});\n", |
| 756 | ); |
| 757 | assert!(kinds.is_empty(), "{kinds:?}\n{text}"); |
| 758 | assert!(text.contains("removes") && text.contains("empties")); |
| 759 | } |
| 760 |
| 761 | /// Random three-way merges against the plain line merge (what git does): |
| 762 | /// where it's clean, the smart merge gives the very same file; where the |
| 763 | /// smart merge settles more, every line either side added is kept, and a |
| 764 | /// clean merge never carries markers. |
| 765 | #[test] |
| 766 | fn smart_merges_never_differ_where_git_is_clean() { |
| 767 | let mut seed: u64 = 0x9E37_79B9_7F4A_7C15; |
| 768 | let mut next = move |n: u64| { |
| 769 | seed ^= seed << 13; |
| 770 | seed ^= seed >> 7; |
| 771 | seed ^= seed << 17; |
| 772 | seed % n |
| 773 | }; |
| 774 | let vocab = [ |
| 775 | "import { a } from \"a\";", |
| 776 | "import { b } from \"b\";", |
| 777 | "import os", |
| 778 | "def f():", |
| 779 | " return 1", |
| 780 | "function g() {", |
| 781 | " return 2;", |
| 782 | "}", |
| 783 | "key: 1", |
| 784 | "other: 2", |
| 785 | "", |
| 786 | "x = 1", |
| 787 | "y = 2", |
| 788 | "// note", |
| 789 | "fn h() {}", |
| 790 | ]; |
| 791 | let rand_text = |len: u64, next: &mut dyn FnMut(u64) -> u64| -> Vec<String> { (0..len).map(|_| vocab[next(vocab.len() as u64) as usize].to_string()).collect() }; |
| 792 | let mut checked = 0; |
| 793 | for case in 0..4000 { |
| 794 | let base = rand_text(next(12), &mut next); |
| 795 | let edit = |next: &mut dyn FnMut(u64) -> u64, lines: &Vec<String>| -> Vec<String> { |
| 796 | let mut out = lines.clone(); |
| 797 | for _ in 0..next(4) { |
| 798 | let at = if out.is_empty() { 0 } else { next(out.len() as u64 + 1) as usize }; |
| 799 | match next(3) { |
| 800 | 0 if at < out.len() => { |
| 801 | out.remove(at); |
| 802 | } |
| 803 | 1 if at < out.len() => out[at] = format!("{} {}", out[at], next(9)), |
| 804 | _ => out.insert(at, vocab[next(vocab.len() as u64) as usize].to_string()), |
| 805 | } |
| 806 | } |
| 807 | out |
| 808 | }; |
| 809 | let ours = edit(&mut next, &base); |
| 810 | let theirs = edit(&mut next, &base); |
| 811 | let join = |l: &Vec<String>| l.iter().map(|s| format!("{s}\n")).collect::<String>(); |
| 812 | let (b, o, t) = (join(&base), join(&ours), join(&theirs)); |
| 813 | for path in ["f.txt", "f.py", "f.js", "f.rs", "f.yaml"] { |
| 814 | let plain = text(b.as_bytes(), o.as_bytes(), t.as_bytes(), "main", "change"); |
| 815 | let smart = text_for(path, b.as_bytes(), o.as_bytes(), t.as_bytes(), "main", "change"); |
| 816 | if plain.conflicts == 0 { |
| 817 | assert_eq!(smart.conflicts, 0, "case {case} {path}"); |
| 818 | assert_eq!(smart.content, plain.content, "case {case} {path}: smart differs where git is clean"); |
| 819 | checked += 1; |
| 820 | } else if smart.conflicts == 0 { |
| 821 | let merged = String::from_utf8(smart.content.clone()).unwrap(); |
| 822 | assert!(!merged.contains("<<<<<<<"), "case {case} {path}"); |
| 823 | let lines: std::collections::HashSet<&str> = merged.lines().collect(); |
| 824 | for side in [&ours, &theirs] { |
| 825 | for l in side.iter().filter(|l| !base.contains(l)) { |
| 826 | assert!(lines.contains(l.as_str()), "case {case} {path}: lost {l:?}\nbase:\n{b}\nours:\n{o}\ntheirs:\n{t}\nmerged:\n{merged}"); |
| 827 | } |
| 828 | } |
| 829 | } |
| 830 | } |
| 831 | } |
| 832 | assert!(checked > 1000); |
| 833 | } |
| 834 |
| 835 | #[test] |
| 836 | fn tree_conflicts() { |
| 837 | let mut src = MemSource::default(); |
| 838 | let base = put_files(&mut src, &[("a.txt", "a\n"), ("gone.txt", "g\n")]); |
| 839 | let ours = put_files(&mut src, &[("a.txt", "main\n")]); |
| 840 | let theirs = put_files(&mut src, &[("a.txt", "change\n"), ("gone.txt", "edited\n")]); |
| 841 | let land = trees(&src, Some(&base), &ours, &theirs, Mode::Land, ("main", "change")).unwrap(); |
| 842 | let mut paths: Vec<_> = land.conflicts.iter().map(|c| (c.path.as_str(), c.kind.as_str())).collect(); |
| 843 | paths.sort(); |
| 844 | assert_eq!(paths, vec![("a.txt", "text"), ("gone.txt", "deleted")]); |
| 845 | let sync = trees(&src, Some(&base), &ours, &theirs, Mode::Sync, ("main 2", "your change x")).unwrap(); |
| 846 | assert_eq!(sync.conflicts.len(), 1); |
| 847 | assert_eq!(sync.notes.len(), 1); |
| 848 | let layered = Layered { first: &sync.objects, second: &src }; |
| 849 | let files = flatten(&layered, &sync.tree).unwrap(); |
| 850 | let a = String::from_utf8(layered.must(&files["a.txt"].id).unwrap().data).unwrap(); |
| 851 | assert!(a.contains("<<<<<<< main 2")); |
| 852 | assert!(files.contains_key("gone.txt")); |
| 853 | } |
| 854 |
| 855 | #[test] |
| 856 | fn fast_paths() { |
| 857 | let mut src = MemSource::default(); |
| 858 | let base = put_files(&mut src, &[("a.txt", "a\n")]); |
| 859 | let theirs = put_files(&mut src, &[("a.txt", "b\n")]); |
| 860 | let m = trees(&src, Some(&base), &base, &theirs, Mode::Land, ("main", "change")).unwrap(); |
| 861 | assert_eq!(m.tree, theirs); |
| 862 | } |
| 863 | } |
| 864 |
| 865 | #[cfg(test)] |
| 866 | mod rename_tests { |
| 867 | use super::*; |
| 868 |
| 869 | fn tree_of(src: &mut MemSource, list: &[(&str, &str)]) -> Id { |
| 870 | let mut map = tree::Files::new(); |
| 871 | for (path, content) in list { |
| 872 | let objects = chunk::file_objects(content.as_bytes()); |
| 873 | let id = objects[0].id(); |
| 874 | for o in objects { |
| 875 | src.put(o); |
| 876 | } |
| 877 | map.insert(path.to_string(), tree::Entry { kind: EntryKind::File, id }); |
| 878 | } |
| 879 | let (id, objects) = tree::build(&map); |
| 880 | for o in objects { |
| 881 | src.put(o); |
| 882 | } |
| 883 | id |
| 884 | } |
| 885 |
| 886 | /// The shortcuts (no listing of main's changes when nothing can have |
| 887 | /// moved; folders merged in one pass) give exactly what the general merge |
| 888 | /// gives: trees, conflicts and notes, landing and syncing. |
| 889 | #[test] |
| 890 | fn shortcuts_merge_as_the_general_path() { |
| 891 | struct Rng(u64); |
| 892 | impl Rng { |
| 893 | fn next(&mut self) -> u64 { |
| 894 | self.0 ^= self.0 >> 12; |
| 895 | self.0 ^= self.0 << 25; |
| 896 | self.0 ^= self.0 >> 27; |
| 897 | self.0.wrapping_mul(0x2545f4914f6cdd1d) |
| 898 | } |
| 899 | fn below(&mut self, n: usize) -> usize { |
| 900 | (self.next() % n as u64) as usize |
| 901 | } |
| 902 | } |
| 903 | let long: String = (0..30).map(|i| format!("line {i}\n")).collect(); |
| 904 | let contents = ["a\n", "b\n", "a\nb\nc\n", "a\nB\nc\n", "A\nb\nc\n", long.as_str(), "x\n"]; |
| 905 | let names = ["a", "b", "c.txt", "d.rs", "e"]; |
| 906 | let edit = |src: &mut MemSource, rng: &mut Rng, tree: &Id, n: usize| -> Id { |
| 907 | let mut put = Vec::new(); |
| 908 | let mut delete = Vec::new(); |
| 909 | for _ in 0..n { |
| 910 | let depth = 1 + rng.below(3); |
| 911 | let p = (0..depth).map(|_| names[rng.below(names.len())]).collect::<Vec<_>>().join("/"); |
| 912 | if rng.below(4) == 0 { |
| 913 | delete.push(p); |
| 914 | } else { |
| 915 | let content = contents[rng.below(contents.len())].as_bytes().to_vec(); |
| 916 | put.push(tree::Put { path: p, kind: if rng.below(9) == 0 { EntryKind::Exec } else { EntryKind::File }, content }); |
| 917 | } |
| 918 | } |
| 919 | let (id, objects) = tree::edit(src, tree, &put, &delete).unwrap().unwrap(); |
| 920 | for o in objects { |
| 921 | src.put(o); |
| 922 | } |
| 923 | id |
| 924 | }; |
| 925 | let mut rng = Rng(0x9e3779b97f4a7c15); |
| 926 | let mut src = MemSource::default(); |
| 927 | src.put(tree::empty()); |
| 928 | let mut differ = 0; |
| 929 | for case in 0..3000 { |
| 930 | let start = edit(&mut src, &mut rng, &tree::empty_id(), 12); |
| 931 | let n = 1 + rng.below(4); |
| 932 | let base = edit(&mut src, &mut rng, &start, n); |
| 933 | let n = rng.below(8); |
| 934 | let ours = edit(&mut src, &mut rng, &base, n); |
| 935 | let n = rng.below(3); |
| 936 | let theirs = edit(&mut src, &mut rng, &base, n); |
| 937 | for mode in [Mode::Land, Mode::Sync] { |
| 938 | let fast = merge_trees(&src, Some(&base), &ours, &theirs, mode, ("main", "change"), false).unwrap(); |
| 939 | let slow = merge_trees(&src, Some(&base), &ours, &theirs, mode, ("main", "change"), true).unwrap(); |
| 940 | assert_eq!(fast.tree, slow.tree, "case {case}"); |
| 941 | assert_eq!(fast.conflicts, slow.conflicts, "case {case}"); |
| 942 | assert_eq!(fast.notes, slow.notes, "case {case}"); |
| 943 | if fast.tree != ours && fast.tree != theirs { |
| 944 | differ += 1; |
| 945 | } |
| 946 | } |
| 947 | } |
| 948 | // Most cases really merged something. |
| 949 | assert!(differ > 2000, "{differ}"); |
| 950 | } |
| 951 |
| 952 | #[test] |
| 953 | fn edits_follow_a_moved_file() { |
| 954 | let mut src = MemSource::default(); |
| 955 | let text: String = (0..30).map(|i| format!("line {i}\n")).collect(); |
| 956 | let base = tree_of(&mut src, &[("src/old.rs", &text)]); |
| 957 | // Main moves the file; the change edits it where it was. |
| 958 | let ours = tree_of(&mut src, &[("src/new.rs", &text)]); |
| 959 | let theirs = tree_of(&mut src, &[("src/old.rs", &text.replace("line 20\n", "line twenty\n"))]); |
| 960 | let m = trees(&src, Some(&base), &ours, &theirs, Mode::Land, ("main", "change")).unwrap(); |
| 961 | assert!(m.clean(), "{:?}", m.conflicts); |
| 962 | let layered = Layered { first: &m.objects, second: &src }; |
| 963 | let flat = tree::flatten(&layered, &m.tree).unwrap(); |
| 964 | assert_eq!(flat.keys().cloned().collect::<Vec<_>>(), vec!["src/new.rs".to_string()]); |
| 965 | let content = chunk::read_file(&layered, &flat["src/new.rs"].id).unwrap(); |
| 966 | assert!(String::from_utf8(content).unwrap().contains("line twenty")); |
| 967 | // And the other way round: the change moves it, main edits it. |
| 968 | let m = trees(&src, Some(&base), &theirs, &ours, Mode::Land, ("main", "change")).unwrap(); |
| 969 | assert!(m.clean(), "{:?}", m.conflicts); |
| 970 | let layered = Layered { first: &m.objects, second: &src }; |
| 971 | let flat = tree::flatten(&layered, &m.tree).unwrap(); |
| 972 | assert_eq!(flat.keys().cloned().collect::<Vec<_>>(), vec!["src/new.rs".to_string()]); |
| 973 | } |
| 974 | } |
| 975 |
