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.fmt16import src.history17import src.remote18import src.snapshot19import src.storage2021pub enum Side {22	mine23	theirs24}2526// Clash is one file both machines changed differently. `stat` is the short27// diff stat the terminal prompt shows, so the choice is informed.28pub struct Clash {29pub mut:30	path         string31	mine         snapshot.FileEntry32	theirs       snapshot.FileEntry33	base         snapshot.FileEntry34	mine_stat    string35	theirs_stat  string36	mine_patch   string37	theirs_patch string38	mine_save    history.Save39	theirs_save  history.Save40}4142pub struct StealPreview {43pub:44	repo      string45	base      string46	local     []history.Save47	remote    []SaveRecord48	changed   int49	automatic int50	identical int51	clashes   []Clash52	yes       bool53	all_side  string54}5556pub struct StealOptions {57pub mut:58	mine   bool // resolve every clash as mine59	theirs bool // resolve every clash as theirs60	// Asked once per clash when neither flag is set. Nil means "nobody to ask".61	ask   fn (clash Clash) Side                      = unsafe { nil }62	guide fn (preview StealPreview) !map[string]Side = unsafe { nil }63	yes   bool64}6566pub struct StealReport {67pub mut:68	repo            string69	forward         bool70	fetched_saves   int71	fetched_objects int72	fetched_events  int73	clashes         []string74	kept_mine       int75	replayed        int76	removed         int77	head            string78	flagged         []events.Flag // incoming saves that are flagged79	// Set when a combine took this machine's saves off the line: loading it80	// brings back the tree from before the steal, less anything stripped.81	previous_head string82	kept_versions []string83}8485pub const dirty_tree = 'save or checkpoint first — steal needs a clean tree'8687// ClashError is a clash nobody was there to decide. It carries the paths because the advice88// depends on the command: `koh steal` takes --mine or --theirs, `koh offer` does not.89pub struct ClashError {90	Error91pub:92	paths []string93}9495pub fn (e ClashError) msg() string {96	return '${e.paths.join(', ')} changed on both machines — run on a terminal to choose, or pass --mine or --theirs'97}9899pub const no_saves_here = 'this folder has files but no saves — steal a repo into an empty folder with "koh steal <name>"'100101// steal brings the remote's new saves in. Inside a repo with its own work this102// may have to combine; a repo with nothing of its own simply fast-forwards.103pub fn steal(store &storage.Store, mut backend remote.Backend, opts StealOptions) !StealReport {104	name := repo_name(store, mut backend)!105	if snapshot.restore_pending(store) {106		return error(snapshot.restore_unfinished)107	}108	head_before := history.head(store)109	// Combining rewrites the working tree, so unsaved work would be lost.110	if dirty(store, head_before)! {111		if head_before == none {112			return error(no_saves_here)113		}114		return error(dirty_tree)115	}116	fetched := fetch_back_to_known(store, mut backend, name)!117	mut report := StealReport{118		repo:            name119		fetched_saves:   fetched.saves.len120		fetched_objects: fetched.repo_objects.len121		fetched_events:  fetched.events_out.len122		head:            fetched.head123	}124	mut local_only := []history.Save{}125	if head := head_before {126		// The remote builds on `base`. If that save is here but no longer on127		// the line, neither line contains the other; jumping to the remote128		// would silently leave this line behind.129		local_only = saves_after(store, head.id, fetched.base) or {130			return error('the remote builds on save ${fetched.base}, which is not on this line — load the save you want, then offer')131		}132	}133	if fetched.base == '' && local_only.len > 0 {134		return error('the remote keeps a different history — it shares no save with this repo')135	}136	if fetched.saves.len > 0 {137		store.begin()!138		write_fetched_records(store, fetched) or {139			store.rollback()140			return err141		}142		store.commit()!143	}144145	strips_before := events.strip_events(store)!.len146	mut clashes := []Clash{}147	mut side_of := map[string]Side{}148	if fetched.saves.len > 0 && local_only.len > 0 {149		clashes = combine_clashes(store, fetched, local_only)!150		report.clashes = clashes.map(it.path)151		if opts.guide != unsafe { nil } {152			side_of = opts.guide(combine_preview(store, name, fetched, local_only, clashes,153				opts.yes, if opts.mine {154					'mine'155				} else if opts.theirs { 'theirs' } else { '' })!)!156		} else {157			// Asked before the write lock: a person thinking must not stall every158			// agent's save on this repo.159			side_of = choose_sides(clashes, opts)!160		}161	}162	for clash in clashes {163		if side_of[clash.path] == .theirs {164			report.kept_versions << '${clash.path}:${local_only.last().id}'165		}166	}167168	store.begin() or { return err }169	// The questions ran without the lock. If a save or an edit landed170	// meanwhile, the answers were about a line that no longer exists.171	if moved := changed_since(store, head_before, strips_before) {172		if moved {173			store.rollback()174			return error('this repo changed while steal was asking — run koh steal again')175		}176	} else {177		store.rollback()178		return err179	}180	final := (write_and_combine(store, fetched, local_only, clashes, side_of, mut report) or {181		store.rollback()182		return err183	})184	files := history.files_of(store, final.id) or {185		store.rollback()186		return err187	}188	snapshot.check_links(store.root, files) or {189		store.rollback()190		return err191	}192	// The files follow the commit; the mark lands with it, in one step.193	// No head before means a fresh clone, whose whole tree is new.194	moved := if head := head_before { final.id != head.id } else { true }195	if moved {196		snapshot.mark_restore(store) or {197			store.rollback()198			return err199		}200	}201	store.commit() or { return err }202	report.head = final.id203	if local_only.len > 0 && report.fetched_saves > 0 {204		report.previous_head = local_only.last().id205	}206	flags := events.latest_flags(store)!207	for record in fetched.saves {208		if flag := flags[record.id] {209			if flag.flagged {210				report.flagged << flag211			}212		}213	}214215	if head := head_before {216		if final.id == head.id {217			// The line did not move, so neither does the working tree.218			return report219		}220		mut wanted := map[string]bool{}221		for file in files {222			wanted[file.path] = true223		}224		mut remove := []string{}225		for file in history.files_of(store, head.id)! {226			if file.path !in wanted {227				remove << file.path228			}229		}230		result := snapshot.restore_files(store, store.root, snapshot.load(store.root), files,231			remove)!232		report.removed = result.removed233	} else {234		snapshot.restore_files(store, store.root, snapshot.load(store.root), files, [])!235	}236	history.refresh_log_md(store)237	return report238}239240// write_and_combine lands a fetch and, when the local line has saves the remote241// lacks, replays them on top of the remote head. It runs inside the caller's242// transaction and returns the new head.243fn write_and_combine(store &storage.Store, fetched Fetched, local_only []history.Save, clashes []Clash, side_of map[string]Side, mut report StealReport) !history.Save {244	write_fetched(store, fetched)!245	if fetched.saves.len == 0 {246		// The remote head is already on this line: level, or this machine is247		// ahead and the offer that follows a steal sends the rest.248		return history.head(store) or { return error('this repo has no head') }249	}250	if local_only.len == 0 {251		// Nothing of ours is missing from the remote: the line simply moves on.252		history.set_head(store, fetched.head)!253		report.forward = true254		return history.head(store) or { return error('the remote head did not land') }255	}256	remote_files := history.files_of(store, fetched.head)!257	mut mine_files := []snapshot.FileEntry{}258	if our_head := history.head(store) {259		mine_files = history.files_of(store, our_head.id)!260	}261262	// A file the remote changed is a clash, decided below, or one this machine263	// left as it was or changed the same way, so the remote's version stands.264	// Replaying this machine's steps on it could only conflict: an edit it265	// later undid would no longer apply.266	base_files := history.files_of(store, fetched.base)!267	settled := changed_paths(base_files, remote_files)268269	// Take the remote's line first, so the replayed saves chain onto it.270	history.set_head(store, fetched.head)!271	mut current := remote_files.clone()272	for save in local_only {273		parent_files := if save.parent != '' {274			history.files_of(store, save.parent)!275		} else {276			[]snapshot.FileEntry{}277		}278		target_files := history.files_of(store, save.id)!279		plan := apply.three_way(current, parent_files, target_files, [], settled)280		if apply.conflicts(plan) {281			return error('combine could not apply ${plan.conflict} — it is not a clash file')282		}283		if plan.applied.len == 0 {284			// Everything this save touched was a file the remote changed.285			continue286		}287		history.record_save(store, '', plan.files, history.SaveInput{288			message:       save.message289			created_at:    save.created_at290			machine:       save.machine291			agent:         save.agent292			session:       save.session293			is_checkpoint: save.is_checkpoint294			replayed_from: save.id295		})!296		current = plan.files.clone()297		report.replayed++298	}299300	mut mine_paths := []string{}301	for clash in clashes {302		if side_of[clash.path] == .mine {303			mine_paths << clash.path304		}305	}306	if mine_paths.len > 0 {307		// One last save puts my versions of the chosen files back.308		final_plan := apply.three_way(current, current, mine_files, mine_paths, [])309		if final_plan.applied.len > 0 {310			history.record_save(store, '', final_plan.files, history.SaveInput{311				message: 'combine: kept mine for ${mine_paths.len} ${if mine_paths.len == 1 {312					'file'313				} else {314					'files'315				}}'316			})!317			report.kept_mine = mine_paths.len318		}319	}320	return history.head(store) or { return error('the combined line has no head') }321}322323// find_clashes lists the files both sides changed, differently. Files changed324// identically on both sides are not clashes: there is nothing to decide.325pub fn find_clashes(base []snapshot.FileEntry, mine []snapshot.FileEntry, theirs []snapshot.FileEntry) []Clash {326	base_map := snapshot.index_files(base)327	mine_map := snapshot.index_files(mine)328	theirs_map := snapshot.index_files(theirs)329	mut paths := mine_map.keys()330	for path in theirs_map.keys() {331		if path !in mine_map {332			paths << path333		}334	}335	paths.sort()336	mut clashes := []Clash{}337	for path in paths {338		here := mine_map[path] or {339			snapshot.FileEntry{340				path: path341			}342		}343		there := theirs_map[path] or {344			snapshot.FileEntry{345				path: path346			}347		}348		was := base_map[path] or {349			snapshot.FileEntry{350				path: path351			}352		}353		if same(here, there) {354			continue355		}356		if same(here, was) || same(there, was) {357			continue358		}359		clashes << Clash{360			path:   path361			mine:   here362			theirs: there363			base:   was364		}365	}366	return clashes367}368369// changed_paths lists the paths whose entry differs between two trees.370fn changed_paths(before []snapshot.FileEntry, after []snapshot.FileEntry) []string {371	was := snapshot.index_files(before)372	now := snapshot.index_files(after)373	mut paths := []string{}374	for path, entry in now {375		if !same(entry, was[path] or { snapshot.FileEntry{} }) {376			paths << path377		}378	}379	for path, _ in was {380		if path !in now {381			paths << path382		}383	}384	return paths385}386387// combine_clashes finds the files both lines changed, with the diff stat each388// prompt shows. It reads the remote head from the fetch, not the store, so it389// can run before anything is written.390fn combine_clashes(store &storage.Store, fetched Fetched, local_only []history.Save) ![]Clash {391	base_files := if fetched.base != '' {392		history.files_of(store, fetched.base)!393	} else {394		[]snapshot.FileEntry{}395	}396	head := history.head(store) or { return []Clash{} }397	// The transaction applies the incoming strips before it replays, so the398	// clashes are found on the trees as they will be then, or the answers399	// would be about files that are no longer there.400	strips := fetched.events_out.filter(it.kind == events.kind_strip)401	// Base and mine are here already, so every strip reaches them (created 0).402	remote_head := fetched.saves.last()403	mut clashes := find_clashes(after_strips(base_files, fetched.base, 0, strips), after_strips(history.files_of(store,404		head.id)!, head.id, 0, strips), after_strips(to_files(remote_head), remote_head.id,405		remote_head.created_at, strips))406	for mut clash in clashes {407		base := fetched_bytes(store, fetched, clash.base)!408		mine := fetched_bytes(store, fetched, clash.mine)!409		theirs := fetched_bytes(store, fetched, clash.theirs)!410		mine_delta := snapshot.diff_bytes(clash.path, 'modified', base, mine)!411		theirs_delta := snapshot.diff_bytes(clash.path, 'modified', base, theirs)!412		clash.mine_stat = delta_stat(mine_delta, clash.mine.size)413		clash.theirs_stat = delta_stat(theirs_delta, clash.theirs.size)414		clash.mine_patch = mine_delta.patch415		clash.theirs_patch = theirs_delta.patch416		clash.mine_save = last_touch(store, local_only, clash.path)!417		clash.theirs_save = last_touch(store, fetched.saves.map(to_save(it)), clash.path)!418	}419	return clashes420}421422fn delta_stat(delta snapshot.Delta, size i64) string {423	if delta.binary {424		return fmt.human_bytes(size)425	}426	return '+${delta.added} -${delta.removed}'427}428429fn last_touch(store &storage.Store, saves []history.Save, path string) !history.Save {430	for index := saves.len - 1; index >= 0; index-- {431		save := saves[index]432		current := snapshot.index_files(history.files_of(store, save.id)!)[path] or {433			snapshot.FileEntry{}434		}435		parent := if save.parent != '' {436			snapshot.index_files(history.files_of(store, save.parent)!)[path] or {437				snapshot.FileEntry{}438			}439		} else {440			snapshot.FileEntry{}441		}442		if !same(current, parent) {443			return save444		}445	}446	return saves.last()447}448449fn combine_preview(store &storage.Store, name string, fetched Fetched, local []history.Save, clashes []Clash, yes bool, all_side string) !StealPreview {450	base := history.files_of(store, fetched.base)!451	mine := history.files_of(store, local.last().id)!452	theirs := history.files_of(store, fetched.head)!453	mine_changed := changed_paths(base, mine)454	theirs_changed := changed_paths(base, theirs)455	mut changed := map[string]bool{}456	for path in mine_changed {457		changed[path] = true458	}459	for path in theirs_changed {460		changed[path] = true461	}462	mut identical := 0463	base_map := snapshot.index_files(base)464	mine_map := snapshot.index_files(mine)465	theirs_map := snapshot.index_files(theirs)466	for path, _ in changed {467		if !same(mine_map[path] or { snapshot.FileEntry{} }, base_map[path] or { snapshot.FileEntry{} })468			&& same(mine_map[path] or { snapshot.FileEntry{} }, theirs_map[path] or { snapshot.FileEntry{} }) {469			identical++470		}471	}472	return StealPreview{473		repo:      name474		base:      fetched.base475		local:     local476		remote:    fetched.saves477		changed:   changed.len478		automatic: changed.len - identical - clashes.len479		identical: identical480		clashes:   clashes481		yes:       yes482		all_side:  all_side483	}484}485486// after_strips is a save's file list once the given strip events are applied,487// by the same rule write_fetched uses.488fn after_strips(files []snapshot.FileEntry, save_id string, created_at i64, strips []events.Event) []snapshot.FileEntry {489	return files.filter(fn [strips, save_id, created_at] (file snapshot.FileEntry) bool {490		return !strips.any(reaches(it, save_id, created_at) && covers(it.path, file.path))491	})492}493494// fetched_bytes reads one side of a clash: from the fetch when it has just495// arrived, else from the store. An absent side is empty.496fn fetched_bytes(store &storage.Store, fetched Fetched, entry snapshot.FileEntry) ![]u8 {497	if entry.hash == '' {498		return []u8{}499	}500	if blob := fetched.repo_objects[entry.hash] {501		return zlib.decompress(blob)!502	}503	return store.get_object(entry.hash)!504}505506fn choose_sides(clashes []Clash, opts StealOptions) !map[string]Side {507	mut sides := map[string]Side{}508	if clashes.len == 0 {509		return sides510	}511	for clash in clashes {512		if opts.mine {513			sides[clash.path] = .mine514			continue515		}516		if opts.theirs {517			sides[clash.path] = .theirs518			continue519		}520		if opts.ask != unsafe { nil } {521			sides[clash.path] = opts.ask(clash)522			continue523		}524		return ClashError{525			paths: clashes.map(it.path)526		}527	}528	return sides529}530531fn same(a snapshot.FileEntry, b snapshot.FileEntry) bool {532	if a.hash == '' && b.hash == '' {533		return true534	}535	return a.hash == b.hash && a.executable == b.executable536}537538fn changed_since(store &storage.Store, before ?history.Save, strips_before int) !bool {539	if events.strip_events(store)!.len != strips_before {540		return true541	}542	now := history.head(store)543	if now or { history.Save{} }.id != before or { history.Save{} }.id {544		return true545	}546	return dirty(store, now)!547}548549// dirty reports whether the working tree holds anything a steal would550// overwrite. With no saves yet, that is every file but the untouched ignore551// list `koh init` wrote.552pub fn dirty(store &storage.Store, head ?history.Save) !bool {553	files := snapshot.walk(store, store.root, snapshot.load(store.root))!554	if saved := head {555		return !snapshot.same_tree(history.files_of(store, saved.id)!, files)556	}557	seed := storage.hash_hex(snapshot.default_ignore.bytes())558	return files.any(it.path != snapshot.ignore_file || it.hash != seed)559}560561// fetch_repo pulls a whole repo — head, saves, objects and events — for562// `koh steal <name>`, which lands a copy in a new folder.563pub fn fetch_repo(mut backend remote.Backend, name string) !Fetched {564	check_format(mut backend, name)!565	remote_head := backend.get(head_key(name))!566	if !remote_head.found {567		return error('the remote has no repo called "${name}"')568	}569	save_ids := backend.list('${name}/saves')!570	object_keys := backend.list('${name}/objects')!571	event_keys := backend.list('${name}/events')!572	mut fetched := Fetched{573		head: remote_head.body.bytestr().trim_space()574	}575	for key in object_keys {576		blob := backend.get(key)!577		if blob.found {578			fetched.repo_objects[os.base(key)] = blob.body579		}580	}581	for key in save_ids {582		body := backend.get(key)!583		if !body.found {584			continue585		}586		record := decode_save(body.body)!587		fetched.saves << record588	}589	fetched.saves = parent_first(fetched.saves)!590	for key in event_keys {591		body := backend.get(key)!592		if body.found {593			fetched.events_out << decode_event(body.body)!594		}595	}596	return fetched597}598599// parent_first orders saves so every parent lands before its children, as the600// foreign key on `parent` demands. Time cannot do it: a replayed save keeps its601// original, older time but sits on a newer parent.602fn parent_first(records []SaveRecord) ![]SaveRecord {603	mut by_id := map[string]SaveRecord{}604	for record in records {605		by_id[record.id] = record606	}607	mut placed := map[string]bool{}608	mut ordered := []SaveRecord{}609	for record in records {610		mut chain := []SaveRecord{}611		mut cursor := record.id612		for cursor != '' && cursor !in placed {613			if chain.len > records.len {614				return error('the save records on the remote form a loop')615			}616			current := by_id[cursor] or { return error('the remote is missing save ${cursor}') }617			chain << current618			cursor = current.parent619		}620		chain.reverse_in_place()621		for current in chain {622			placed[current.id] = true623			ordered << current624		}625	}626	return ordered627}