steal.v

1//! Stealing: bringing another machine's saves in, and combining when both2//! machines moved.3//!4//! The order is always the same, and it is what makes an interrupted steal5//! harmless: read everything from the remote first, then land it in one6//! transaction, then write the working tree. Divergence is resolved per file —7//! a clash is never merged line by line, it is chosen.89module exchange1011import compress.zlib12import os13import src.apply14import src.events15import src.history16import src.remote17import src.snapshot18import src.storage1920pub enum Side {21	mine22	theirs23}2425// Clash is one file both machines changed differently. `stat` is the short26// diff stat the terminal prompt shows, so the choice is informed.27pub struct Clash {28pub mut:29	path   string30	mine   snapshot.FileEntry31	theirs snapshot.FileEntry32	base   snapshot.FileEntry33	stat   string34}3536pub struct StealOptions {37pub mut:38	mine   bool // resolve every clash as mine39	theirs bool // resolve every clash as theirs40	// Asked once per clash when neither flag is set. Nil means "nobody to ask".41	ask fn (clash Clash) Side = unsafe { nil }42}4344pub struct StealReport {45pub mut:46	repo            string47	forward         bool48	fetched_saves   int49	fetched_objects int50	fetched_events  int51	clashes         []string52	kept_mine       int53	replayed        int54	removed         int55	head            string56	flagged         []events.Flag // incoming saves that are flagged57	// Set when a combine took this machine's saves off the line: loading it58	// brings back the tree from before the steal, less anything stripped.59	previous_head string60}6162pub const dirty_tree = 'save or checkpoint first — steal needs a clean tree'63pub const no_saves_here = 'this folder has files but no saves — steal a repo into an empty folder with "koh steal <name>"'6465// steal brings the remote's new saves in. Inside a repo with its own work this66// may have to combine; a repo with nothing of its own simply fast-forwards.67pub fn steal(store &storage.Store, mut backend remote.Backend, opts StealOptions) !StealReport {68	name := repo_name(store, mut backend)!69	if snapshot.restore_pending(store) {70		return error(snapshot.restore_unfinished)71	}72	head_before := history.head(store)73	// Combining rewrites the working tree, so unsaved work would be lost.74	if dirty(store, head_before)! {75		if head_before == none {76			return error(no_saves_here)77		}78		return error(dirty_tree)79	}80	fetched := fetch_back_to_known(store, mut backend, name)!81	mut report := StealReport{82		repo:            name83		fetched_saves:   fetched.saves.len84		fetched_objects: fetched.repo_objects.len85		fetched_events:  fetched.events_out.len86		head:            fetched.head87	}88	mut local_only := []history.Save{}89	if head := head_before {90		// The remote builds on `base`. If that save is here but no longer on91		// the line, neither line contains the other; jumping to the remote92		// would silently leave this line behind.93		local_only = saves_after(store, head.id, fetched.base) or {94			return error('the remote builds on save ${fetched.base}, which is not on this line — load the save you want, then offer')95		}96	}97	if fetched.base == '' && local_only.len > 0 {98		return error('the remote keeps a different history — it shares no save with this repo')99	}100101	strips_before := events.strip_events(store)!.len102	mut clashes := []Clash{}103	mut side_of := map[string]Side{}104	if fetched.saves.len > 0 && local_only.len > 0 {105		clashes = combine_clashes(store, fetched)!106		report.clashes = clashes.map(it.path)107		// Asked before the write lock: a person thinking must not stall every108		// agent's save on this repo.109		side_of = choose_sides(clashes, opts)!110	}111112	store.begin() or { return err }113	// The questions ran without the lock. If a save or an edit landed114	// meanwhile, the answers were about a line that no longer exists.115	if moved := changed_since(store, head_before, strips_before) {116		if moved {117			store.rollback()118			return error('this repo changed while steal was asking — run koh steal again')119		}120	} else {121		store.rollback()122		return err123	}124	final := (write_and_combine(store, fetched, local_only, clashes, side_of, mut report) or {125		store.rollback()126		return err127	})128	files := history.files_of(store, final.id) or {129		store.rollback()130		return err131	}132	snapshot.check_links(store.root, files) or {133		store.rollback()134		return err135	}136	// The files follow the commit; the mark lands with it, in one step.137	// No head before means a fresh clone, whose whole tree is new.138	moved := if head := head_before { final.id != head.id } else { true }139	if moved {140		snapshot.mark_restore(store) or {141			store.rollback()142			return err143		}144	}145	store.commit() or { return err }146	report.head = final.id147	if local_only.len > 0 && report.fetched_saves > 0 {148		report.previous_head = local_only.last().id149	}150	flags := events.latest_flags(store)!151	for record in fetched.saves {152		if flag := flags[record.id] {153			if flag.flagged {154				report.flagged << flag155			}156		}157	}158159	if head := head_before {160		if final.id == head.id {161			// The line did not move, so neither does the working tree.162			return report163		}164		mut wanted := map[string]bool{}165		for file in files {166			wanted[file.path] = true167		}168		mut remove := []string{}169		for file in history.files_of(store, head.id)! {170			if file.path !in wanted {171				remove << file.path172			}173		}174		result := snapshot.restore_files(store, store.root, snapshot.load(store.root), files,175			remove)!176		report.removed = result.removed177	} else {178		snapshot.restore_files(store, store.root, snapshot.load(store.root), files, [])!179	}180	history.refresh_log_md(store)181	return report182}183184// write_and_combine lands a fetch and, when the local line has saves the remote185// lacks, replays them on top of the remote head. It runs inside the caller's186// transaction and returns the new head.187fn write_and_combine(store &storage.Store, fetched Fetched, local_only []history.Save, clashes []Clash, side_of map[string]Side, mut report StealReport) !history.Save {188	write_fetched(store, fetched)!189	if fetched.saves.len == 0 {190		// The remote head is already on this line: level, or this machine is191		// ahead and the offer that follows a steal sends the rest.192		return history.head(store) or { return error('this repo has no head') }193	}194	if local_only.len == 0 {195		// Nothing of ours is missing from the remote: the line simply moves on.196		history.set_head(store, fetched.head)!197		report.forward = true198		return history.head(store) or { return error('the remote head did not land') }199	}200	remote_files := history.files_of(store, fetched.head)!201	mut mine_files := []snapshot.FileEntry{}202	if our_head := history.head(store) {203		mine_files = history.files_of(store, our_head.id)!204	}205206	// A file the remote changed is a clash, decided below, or one this machine207	// left as it was or changed the same way, so the remote's version stands.208	// Replaying this machine's steps on it could only conflict: an edit it209	// later undid would no longer apply.210	base_files := history.files_of(store, fetched.base)!211	settled := changed_paths(base_files, remote_files)212213	// Take the remote's line first, so the replayed saves chain onto it.214	history.set_head(store, fetched.head)!215	mut current := remote_files.clone()216	for save in local_only {217		parent_files := if save.parent != '' {218			history.files_of(store, save.parent)!219		} else {220			[]snapshot.FileEntry{}221		}222		target_files := history.files_of(store, save.id)!223		plan := apply.three_way(current, parent_files, target_files, [], settled)224		if apply.conflicts(plan) {225			return error('combine could not apply ${plan.conflict} — it is not a clash file')226		}227		if plan.applied.len == 0 {228			// Everything this save touched was a file the remote changed.229			continue230		}231		history.record_save(store, '', plan.files, history.SaveInput{232			message:       save.message233			created_at:    save.created_at234			machine:       save.machine235			agent:         save.agent236			session:       save.session237			is_checkpoint: save.is_checkpoint238			replayed_from: save.id239		})!240		current = plan.files.clone()241		report.replayed++242	}243244	mut mine_paths := []string{}245	for clash in clashes {246		if side_of[clash.path] == .mine {247			mine_paths << clash.path248		}249	}250	if mine_paths.len > 0 {251		// One last save puts my versions of the chosen files back.252		final_plan := apply.three_way(current, current, mine_files, mine_paths, [])253		if final_plan.applied.len > 0 {254			history.record_save(store, '', final_plan.files, history.SaveInput{255				message: 'combine: kept mine for ${mine_paths.len} ${if mine_paths.len == 1 {256					'file'257				} else {258					'files'259				}}'260			})!261			report.kept_mine = mine_paths.len262		}263	}264	return history.head(store) or { return error('the combined line has no head') }265}266267// find_clashes lists the files both sides changed, differently. Files changed268// identically on both sides are not clashes: there is nothing to decide.269pub fn find_clashes(base []snapshot.FileEntry, mine []snapshot.FileEntry, theirs []snapshot.FileEntry) []Clash {270	base_map := snapshot.index_files(base)271	mine_map := snapshot.index_files(mine)272	theirs_map := snapshot.index_files(theirs)273	mut paths := mine_map.keys()274	for path in theirs_map.keys() {275		if path !in mine_map {276			paths << path277		}278	}279	paths.sort()280	mut clashes := []Clash{}281	for path in paths {282		here := mine_map[path] or {283			snapshot.FileEntry{284				path: path285			}286		}287		there := theirs_map[path] or {288			snapshot.FileEntry{289				path: path290			}291		}292		was := base_map[path] or {293			snapshot.FileEntry{294				path: path295			}296		}297		if same(here, there) {298			continue299		}300		if same(here, was) || same(there, was) {301			continue302		}303		clashes << Clash{304			path:   path305			mine:   here306			theirs: there307			base:   was308		}309	}310	return clashes311}312313// changed_paths lists the paths whose entry differs between two trees.314fn changed_paths(before []snapshot.FileEntry, after []snapshot.FileEntry) []string {315	was := snapshot.index_files(before)316	now := snapshot.index_files(after)317	mut paths := []string{}318	for path, entry in now {319		if !same(entry, was[path] or { snapshot.FileEntry{} }) {320			paths << path321		}322	}323	for path, _ in was {324		if path !in now {325			paths << path326		}327	}328	return paths329}330331// combine_clashes finds the files both lines changed, with the diff stat each332// prompt shows. It reads the remote head from the fetch, not the store, so it333// can run before anything is written.334fn combine_clashes(store &storage.Store, fetched Fetched) ![]Clash {335	base_files := if fetched.base != '' {336		history.files_of(store, fetched.base)!337	} else {338		[]snapshot.FileEntry{}339	}340	head := history.head(store) or { return []Clash{} }341	// The transaction applies the incoming strips before it replays, so the342	// clashes are found on the trees as they will be then, or the answers343	// would be about files that are no longer there.344	strips := fetched.events_out.filter(it.kind == events.kind_strip)345	// Base and mine are here already, so every strip reaches them (created 0).346	remote_head := fetched.saves.last()347	mut clashes := find_clashes(after_strips(base_files, fetched.base, 0, strips), after_strips(history.files_of(store,348		head.id)!, head.id, 0, strips), after_strips(to_files(remote_head), remote_head.id,349		remote_head.created_at, strips))350	for mut clash in clashes {351		mine := fetched_bytes(store, fetched, clash.mine)!352		theirs := fetched_bytes(store, fetched, clash.theirs)!353		delta := snapshot.diff_bytes(clash.path, 'modified', mine, theirs)!354		clash.stat = if delta.binary { 'binary' } else { '+${delta.added} -${delta.removed}' }355	}356	return clashes357}358359// after_strips is a save's file list once the given strip events are applied,360// by the same rule write_fetched uses.361fn after_strips(files []snapshot.FileEntry, save_id string, created_at i64, strips []events.Event) []snapshot.FileEntry {362	return files.filter(fn [strips, save_id, created_at] (file snapshot.FileEntry) bool {363		return !strips.any(reaches(it, save_id, created_at) && covers(it.path, file.path))364	})365}366367// fetched_bytes reads one side of a clash: from the fetch when it has just368// arrived, else from the store. An absent side is empty.369fn fetched_bytes(store &storage.Store, fetched Fetched, entry snapshot.FileEntry) ![]u8 {370	if entry.hash == '' {371		return []u8{}372	}373	if blob := fetched.repo_objects[entry.hash] {374		return zlib.decompress(blob)!375	}376	return store.get_object(entry.hash)!377}378379fn choose_sides(clashes []Clash, opts StealOptions) !map[string]Side {380	mut sides := map[string]Side{}381	if clashes.len == 0 {382		return sides383	}384	for clash in clashes {385		if opts.mine {386			sides[clash.path] = .mine387			continue388		}389		if opts.theirs {390			sides[clash.path] = .theirs391			continue392		}393		if opts.ask != unsafe { nil } {394			sides[clash.path] = opts.ask(clash)395			continue396		}397		paths := clashes.map(it.path).join(', ')398		return error('${paths} changed on both machines — run on a terminal to choose, or pass --mine or --theirs')399	}400	return sides401}402403fn same(a snapshot.FileEntry, b snapshot.FileEntry) bool {404	if a.hash == '' && b.hash == '' {405		return true406	}407	return a.hash == b.hash && a.executable == b.executable408}409410fn changed_since(store &storage.Store, before ?history.Save, strips_before int) !bool {411	if events.strip_events(store)!.len != strips_before {412		return true413	}414	now := history.head(store)415	if now or { history.Save{} }.id != before or { history.Save{} }.id {416		return true417	}418	return dirty(store, now)!419}420421// dirty reports whether the working tree holds anything a steal would422// overwrite. With no saves yet, that is every file but the untouched ignore423// list `koh init` wrote.424pub fn dirty(store &storage.Store, head ?history.Save) !bool {425	files := snapshot.walk(store, store.root, snapshot.load(store.root))!426	if saved := head {427		return !snapshot.same_tree(history.files_of(store, saved.id)!, files)428	}429	seed := storage.hash_hex(snapshot.default_ignore.bytes())430	return files.any(it.path != snapshot.ignore_file || it.hash != seed)431}432433// fetch_repo pulls a whole repo — head, saves, objects and events — for434// `koh steal <name>`, which lands a copy in a new folder.435pub fn fetch_repo(mut backend remote.Backend, name string) !Fetched {436	check_format(mut backend, name)!437	remote_head := backend.get(head_key(name))!438	if !remote_head.found {439		return error('the remote has no repo called "${name}"')440	}441	save_ids := backend.list('${name}/saves')!442	object_keys := backend.list('${name}/objects')!443	event_keys := backend.list('${name}/events')!444	mut fetched := Fetched{445		head: remote_head.body.bytestr().trim_space()446	}447	for key in object_keys {448		blob := backend.get(key)!449		if blob.found {450			fetched.repo_objects[os.base(key)] = blob.body451		}452	}453	for key in save_ids {454		body := backend.get(key)!455		if !body.found {456			continue457		}458		record := decode_save(body.body)!459		fetched.saves << record460	}461	fetched.saves = parent_first(fetched.saves)!462	for key in event_keys {463		body := backend.get(key)!464		if body.found {465			fetched.events_out << decode_event(body.body)!466		}467	}468	return fetched469}470471// parent_first orders saves so every parent lands before its children, as the472// foreign key on `parent` demands. Time cannot do it: a replayed save keeps its473// original, older time but sits on a newer parent.474fn parent_first(records []SaveRecord) ![]SaveRecord {475	mut by_id := map[string]SaveRecord{}476	for record in records {477		by_id[record.id] = record478	}479	mut placed := map[string]bool{}480	mut ordered := []SaveRecord{}481	for record in records {482		mut chain := []SaveRecord{}483		mut cursor := record.id484		for cursor != '' && cursor !in placed {485			if chain.len > records.len {486				return error('the save records on the remote form a loop')487			}488			current := by_id[cursor] or { return error('the remote is missing save ${cursor}') }489			chain << current490			cursor = current.parent491		}492		chain.reverse_in_place()493		for current in chain {494			placed[current.id] = true495			ordered << current496		}497	}498	return ordered499}