@4 Three-way merge: land changes built on an older main, and rebuild local steps on sync

by claude for antonky · landed by antonky · 18d ago · from #3 · files at @4

Files

msrc/cli.rs+14 −6 msrc/lib.rs+1 −0 asrc/merge.rs+278 −0 msrc/store.rs+39 −19

src/cli.rsmodified+14 −6

src/lib.rsmodified+1 −0

src/merge.rsadded+278 −0

src/store.rsmodified+39 −19


686	686	println!("already at @{}", local.base);
687	687	return Ok(());
688	688	}
689		if !local.steps.is_empty() {
690		return e!("there are local steps on @{}; rebuilding them on @{} needs merging, which isn't built yet", local.base, p.tip());
691		}
692		let (_, _, pending) = working_changes(&store, &local)?;
	689	let (current, _, pending) = working_changes(&store, &local)?;
693	690	if !pending.is_empty() {
694	691	return e!("the working directory has changes; record them as a step first");
695	692	}
696	693	let from = p.point(local.base).map(\|pt\| pt.snapshot).ok_or("base missing")?;
697	694	let tip = p.points.last().unwrap();
698		workdir::materialize(&store.objects, &tip.snapshot, &local.root, Some(&from)).map_err(\|e\| e.to_string())?;
	695	// Replay the local steps onto the tip; the working directory follows the last one.
	696	let snapshots: Vec<Id> = local.steps.iter().map(\|st\| st.snapshot).collect();
	697	let rebuilt = match crate::merge::rebuild(&store.objects, &from, &snapshots, &tip.snapshot).map_err(\|e\| e.to_string())? {
	698	Ok(r) => r,
	699	Err((i, paths)) => return e!("step {} ({}) conflicts with @{} in: {}", i + 1, local.steps[i].message, tip.n, paths.join(", ")),
	700	};
	701	let target = rebuilt.last().copied().unwrap_or(tip.snapshot);
	702	workdir::materialize(&store.objects, &target, &local.root, Some(&current)).map_err(\|e\| e.to_string())?;
	703	for (st, snap) in local.steps.iter_mut().zip(rebuilt) {
	704	st.snapshot = snap;
	705	}
699	706	local.base = tip.n;
700	707	local.save()?;
701		println!("now at @{}", tip.n);
	708	let kept = local.steps.len();
	709	println!("now at @{}{}", tip.n, if kept > 0 { format!(", {kept} local step{} rebuilt on it", if kept == 1 { "" } else { "s" }) } else { String::new() });
702	710	Ok(())
703	711	}
704	712


7	7	pub mod ignore;
8	8	pub mod json;
9	9	pub mod log;
	10	pub mod merge;
10	11	pub mod model;
11	12	pub mod objects;
12	13	pub mod random;


21	21	Damaged { record: u64, reason: String },
22	22	/// The request isn't allowed or doesn't make sense.
23	23	Refused(String),
24		/// Landing needs the change rebuilt on the current tip first.
25		Behind { base: u64, tip: u64 },
	24	/// The change can't be rebuilt on the current tip without someone resolving these paths.
	25	Conflict { step: usize, paths: Vec<String> },
26	26	}
27	27
28	28	impl std::fmt::Display for Error {

33	33	Error::Io(e) => write!(f, "{e}"),
34	34	Error::Damaged { record, reason } => write!(f, "log record {record} is damaged: {reason}"),
35	35	Error::Refused(r) => write!(f, "{r}"),
36		Error::Behind { base, tip } => write!(f, "built on point {base}, but main is at {tip}; rebuild on the tip first"),
	36	Error::Conflict { step, paths } => write!(f, "step {} conflicts with main in {}", step + 1, paths.join(", ")),
37	37	}
38	38	}
39	39	}

258	258	}
259	259	let c = p.change(change).ok_or_else(\|\| Error::Refused(format!("no change #{change}")))?;
260	260	let rev = c.latest().ok_or_else(\|\| Error::Refused(format!("#{change} has no revisions")))?;
261		if rev.base != p.tip() {
262		return Err(Error::Behind { base: rev.base, tip: p.tip() });
263		}
264		let first = p.tip() + 1;
265		let count = rev.steps.len() as u64;
266		let snapshots: Vec<Value> = rev.steps.iter().map(\|s\| id_to_json(&s.snapshot)).collect();
	261	let tip = p.tip();
	262	let steps: Vec<Id> = rev.steps.iter().map(\|s\| s.snapshot).collect();
	263	// Built on an older point: replay each step's edits onto the current tip.
	264	let snapshots = if rev.base == tip {
	265	steps
	266	} else {
	267	let from = p.point(rev.base).map(\|pt\| pt.snapshot).ok_or_else(\|\| Error::Refused("base point missing".into()))?;
	268	let onto = p.point(tip).map(\|pt\| pt.snapshot).unwrap();
	269	match crate::merge::rebuild(&self.objects, &from, &steps, &onto)? {
	270	Ok(rebuilt) => rebuilt,
	271	Err((step, paths)) => return Err(Error::Conflict { step, paths }),
	272	}
	273	};
	274	let first = tip + 1;
	275	let count = snapshots.len() as u64;
	276	let snapshots: Vec<Value> = snapshots.iter().map(id_to_json).collect();
267	277	let revision = rev.number as u64;
268	278	self.write(
269	279	by,

403	413	}
404	414
405	415	#[test]
406		fn landing_behind_the_tip_is_refused() {
	416	fn landing_on_a_moved_main() {
407	417	let dir = TestDir::new("store-behind");
408	418	let (mut store, me, _) = setup(&dir);
409	419	let owner = Actor::person("anton");
410		let t = tree(&store, &[("README", "a")]);
411		let step = \|id: &str\| vec![Step { id: id.into(), snapshot: t, message: "m".into() }];
	420	// Both changes start from @1 (README = "hello").
	421	let ta = tree(&store, &[("README", "hello"), ("a.txt", "from a\n")]);
	422	let tb = tree(&store, &[("README", "hello"), ("b.txt", "from b\n")]);
	423	let tc = tree(&store, &[("README", "clash")]);
412	424	let a = store.open_change(&me, "anton", "grove", "a").unwrap();
413	425	let b = store.open_change(&me, "anton", "grove", "b").unwrap();
414		store.revise(&me, "anton", "grove", a, 1, &step("x"), None).unwrap();
415		store.revise(&me, "anton", "grove", b, 1, &step("y"), None).unwrap();
416		store.set_state(&me, "anton", "grove", a, ChangeState::Proposed).unwrap();
417		store.set_state(&me, "anton", "grove", b, ChangeState::Proposed).unwrap();
	426	let c = store.open_change(&me, "anton", "grove", "c").unwrap();
	427	let tl = tree(&store, &[("README", "landed")]);
	428	for (n, t) in [(a, tl), (b, tb), (c, tc)] {
	429	store.revise(&me, "anton", "grove", n, 1, &[Step { id: "s".into(), snapshot: t, message: "m".into() }], None).unwrap();
	430	store.set_state(&me, "anton", "grove", n, ChangeState::Proposed).unwrap();
	431	}
418	432	store.land(&owner, "anton", "grove", a).unwrap();
419		assert!(matches!(store.land(&owner, "anton", "grove", b), Err(Error::Behind { base: 1, tip: 2 })));
420		// Nothing changed for b.
421		assert_eq!(store.project("anton", "grove").unwrap().change(b).unwrap().state, ChangeState::Proposed);
	433	// b touched other files: it's rebuilt on @2 and lands.
	434	assert_eq!(store.land(&owner, "anton", "grove", b).unwrap(), (3, 3));
	435	let p = store.project("anton", "grove").unwrap();
	436	assert_eq!(p.point(3).unwrap().snapshot, tree(&store, &[("README", "landed"), ("b.txt", "from b\n")]));
	437	// c changed README differently from what landed: a conflict, and nothing changes.
	438	let before = store.state().records;
	439	assert!(matches!(store.land(&owner, "anton", "grove", c), Err(Error::Conflict { step: 0, .. })));
	440	assert_eq!(store.state().records, before);
	441	assert_eq!(store.project("anton", "grove").unwrap().change(c).unwrap().state, ChangeState::Proposed);
422	442	}
423	443
424	444	#[test]

	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	}