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      history.Save46	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	// Shown the whole combine and asked about every clash. Nil means "nobody to ask".61	guide fn (preview StealPreview) !map[string]Side = unsafe { nil }62	yes   bool63}6465pub struct StealReport {66pub mut:67	repo            string68	forward         bool69	fetched_saves   int70	fetched_objects int71	fetched_events  int72	clashes         []string73	kept_mine       int74	replayed        int75	removed         int76	head            string77	flagged         []events.Flag // incoming saves that are flagged78	// Set when a combine took this machine's saves off the line: loading it79	// brings back the tree from before the steal, less anything stripped.80	previous_head string81	kept_versions []string82}8384pub const dirty_tree = 'save or checkpoint first — steal needs a clean tree'8586// ClashError is a clash nobody was there to decide. It carries the paths because the advice87// depends on the command: `koh steal` takes --mine or --theirs, `koh offer` does not.88pub struct ClashError {89	Error90pub:91	paths []string92}9394pub fn (e ClashError) msg() string {95	return '${e.paths.join(', ')} changed on both machines — run on a terminal to choose, or pass --mine or --theirs'96}9798pub const no_saves_here = 'this folder has files but no saves — steal a repo into an empty folder with "koh steal <name>"'99100// steal brings the remote's new saves in. Inside a repo with its own work this101// may have to combine; a repo with nothing of its own simply fast-forwards.102pub fn steal(store &storage.Store, mut backend remote.Backend, opts StealOptions) !StealReport {103	name := repo_name(store, mut backend)!104	if snapshot.restore_pending(store) {105		return error(snapshot.restore_unfinished)106	}107	head_before := history.head(store)108	// Combining rewrites the working tree, so unsaved work would be lost.109	if dirty(store, head_before)! {110		if head_before == none {111			return error(no_saves_here)112		}113		return error(dirty_tree)114	}115	fetched := fetch_back_to_known(store, mut backend, name)!116	mut report := StealReport{117		repo:            name118		fetched_saves:   fetched.saves.len119		fetched_objects: fetched.repo_objects.len120		fetched_events:  fetched.events_out.len121		head:            fetched.head122	}123	mut local_only := []history.Save{}124	if head := head_before {125		// The remote builds on `base`. If that save is here but no longer on126		// the line, neither line contains the other; jumping to the remote127		// would silently leave this line behind.128		local_only = saves_after(store, head.id, fetched.base) or {129			return error('the remote builds on save ${fetched.base}, which is not on this line — load the save you want, then offer')130		}131	}132	if fetched.base == '' && local_only.len > 0 {133		return error('the remote keeps a different history — it shares no save with this repo')134	}135	if fetched.saves.len > 0 {136		store.begin()!137		write_fetched_records(store, fetched) or {138			store.rollback()139			return err140		}141		store.commit()!142	}143144	strips_before := events.strip_events(store)!.len145	mut clashes := []Clash{}146	mut side_of := map[string]Side{}147	if fetched.saves.len > 0 && local_only.len > 0 {148		clashes = combine_clashes(store, fetched, local_only)!149		report.clashes = clashes.map(it.path)150		if opts.guide != unsafe { nil } {151			side_of = opts.guide(combine_preview(store, name, fetched, local_only, clashes,152				opts.yes, if opts.mine {153					'mine'154				} else if opts.theirs { 'theirs' } else { '' })!)!155		} else {156			// Asked before the write lock: a person thinking must not stall every157			// agent's save on this repo.158			side_of = choose_sides(clashes, opts)!159		}160	}161	for clash in clashes {162		if side_of[clash.path] == .theirs {163			report.kept_versions << '${clash.path}:${local_only.last().id}'164		}165	}166167	store.begin() or { return err }168	// The questions ran without the lock. If a save or an edit landed169	// meanwhile, the answers were about a line that no longer exists.170	if moved := changed_since(store, head_before, strips_before) {171		if moved {172			store.rollback()173			return error('this repo changed while steal was asking — run koh steal again')174		}175	} else {176		store.rollback()177		return err178	}179	final := (write_and_combine(store, fetched, local_only, clashes, side_of, mut report) or {180		store.rollback()181		return err182	})183	files := history.files_of(store, final.id) or {184		store.rollback()185		return err186	}187	snapshot.check_links(store.root, files) or {188		store.rollback()189		return err190	}191	// The files follow the commit; the mark lands with it, in one step.192	// No head before means a fresh clone, whose whole tree is new.193	moved := if head := head_before { final.id != head.id } else { true }194	if moved {195		snapshot.mark_restore(store) or {196			store.rollback()197			return err198		}199	}200	store.commit() or { return err }201	report.head = final.id202	if local_only.len > 0 && report.fetched_saves > 0 {203		report.previous_head = local_only.last().id204	}205	flags := events.latest_flags(store)!206	for record in fetched.saves {207		if flag := flags[record.id] {208			if flag.flagged {209				report.flagged << flag210			}211		}212	}213214	if head := head_before {215		if final.id == head.id {216			// The line did not move, so neither does the working tree.217			return report218		}219		mut wanted := map[string]bool{}220		for file in files {221			wanted[file.path] = true222		}223		mut remove := []string{}224		for file in history.files_of(store, head.id)! {225			if file.path !in wanted {226				remove << file.path227			}228		}229		result := snapshot.restore_files(store, store.root, snapshot.load(store.root), files,230			remove)!231		report.removed = result.removed232	} else {233		snapshot.restore_files(store, store.root, snapshot.load(store.root), files, [])!234	}235	history.refresh_log_md(store)236	return report237}238239// write_and_combine lands a fetch and, when the local line has saves the remote240// lacks, replays them on top of the remote head. It runs inside the caller's241// transaction and returns the new head.242fn write_and_combine(store &storage.Store, fetched Fetched, local_only []history.Save, clashes []Clash, side_of map[string]Side, mut report StealReport) !history.Save {243	write_fetched(store, fetched)!244	if fetched.saves.len == 0 {245		// The remote head is already on this line: level, or this machine is246		// ahead and the offer that follows a steal sends the rest.247		return history.head(store) or { return error('this repo has no head') }248	}249	if local_only.len == 0 {250		// Nothing of ours is missing from the remote: the line simply moves on.251		history.set_head(store, fetched.head)!252		report.forward = true253		return history.head(store) or { return error('the remote head did not land') }254	}255	remote_files := history.files_of(store, fetched.head)!256	mut mine_files := []snapshot.FileEntry{}257	if our_head := history.head(store) {258		mine_files = history.files_of(store, our_head.id)!259	}260261	// A file the remote changed is a clash, decided below, or one this machine262	// left as it was or changed the same way, so the remote's version stands.263	// Replaying this machine's steps on it could only conflict: an edit it264	// later undid would no longer apply.265	base_files := history.files_of(store, fetched.base)!266	settled := changed_paths(base_files, remote_files)267268	// Take the remote's line first, so the replayed saves chain onto it.269	history.set_head(store, fetched.head)!270	mut current := remote_files.clone()271	for save in local_only {272		parent_files := if save.parent != '' {273			history.files_of(store, save.parent)!274		} else {275			[]snapshot.FileEntry{}276		}277		target_files := history.files_of(store, save.id)!278		plan := apply.three_way(current, parent_files, target_files, [], settled)279		if apply.conflicts(plan) {280			return error('combine could not apply ${plan.conflict} — it is not a clash file')281		}282		if plan.applied.len == 0 {283			// Everything this save touched was a file the remote changed.284			continue285		}286		history.record_save(store, '', plan.files, history.SaveInput{287			message:       save.message288			created_at:    save.created_at289			machine:       save.machine290			agent:         save.agent291			session:       save.session292			is_checkpoint: save.is_checkpoint293			replayed_from: save.id294		})!295		current = plan.files.clone()296		report.replayed++297	}298299	mut mine_paths := []string{}300	for clash in clashes {301		if side_of[clash.path] == .mine {302			mine_paths << clash.path303		}304	}305	if mine_paths.len > 0 {306		// One last save puts my versions of the chosen files back.307		final_plan := apply.three_way(current, current, mine_files, mine_paths, [])308		if final_plan.applied.len > 0 {309			history.record_save(store, '', final_plan.files, history.SaveInput{310				message: 'combine: kept mine for ${mine_paths.len} ${if mine_paths.len == 1 {311					'file'312				} else {313					'files'314				}}'315			})!316			report.kept_mine = mine_paths.len317		}318	}319	return history.head(store) or { return error('the combined line has no head') }320}321322// find_clashes lists the files both sides changed, differently. Files changed323// identically on both sides are not clashes: there is nothing to decide.324pub fn find_clashes(base []snapshot.FileEntry, mine []snapshot.FileEntry, theirs []snapshot.FileEntry) []Clash {325	base_map := snapshot.index_files(base)326	mine_map := snapshot.index_files(mine)327	theirs_map := snapshot.index_files(theirs)328	mut paths := mine_map.keys()329	for path in theirs_map.keys() {330		if path !in mine_map {331			paths << path332		}333	}334	paths.sort()335	mut clashes := []Clash{}336	for path in paths {337		here := mine_map[path] or {338			snapshot.FileEntry{339				path: path340			}341		}342		there := theirs_map[path] or {343			snapshot.FileEntry{344				path: path345			}346		}347		was := base_map[path] or {348			snapshot.FileEntry{349				path: path350			}351		}352		if same(here, there) {353			continue354		}355		if same(here, was) || same(there, was) {356			continue357		}358		clashes << Clash{359			path:   path360			mine:   here361			theirs: there362			base:   was363		}364	}365	return clashes366}367368// changed_paths lists the paths whose entry differs between two trees.369fn changed_paths(before []snapshot.FileEntry, after []snapshot.FileEntry) []string {370	was := snapshot.index_files(before)371	now := snapshot.index_files(after)372	mut paths := []string{}373	for path, entry in now {374		if !same(entry, was[path] or { snapshot.FileEntry{} }) {375			paths << path376		}377	}378	for path, _ in was {379		if path !in now {380			paths << path381		}382	}383	return paths384}385386// combine_clashes finds the files both lines changed, with the diff stat each387// prompt shows. It reads the remote head from the fetch, not the store, so it388// can run before anything is written.389fn combine_clashes(store &storage.Store, fetched Fetched, local_only []history.Save) ![]Clash {390	base_files := if fetched.base != '' {391		history.files_of(store, fetched.base)!392	} else {393		[]snapshot.FileEntry{}394	}395	head := history.head(store) or { return []Clash{} }396	// The transaction applies the incoming strips before it replays, so the397	// clashes are found on the trees as they will be then, or the answers398	// would be about files that are no longer there.399	strips := fetched.events_out.filter(it.kind == events.kind_strip)400	// Base and mine are here already, so every strip reaches them (created 0).401	remote_head := fetched.saves.last()402	mut clashes := find_clashes(after_strips(base_files, fetched.base, 0, strips), after_strips(history.files_of(store,403		head.id)!, head.id, 0, strips), after_strips(to_files(remote_head), remote_head.id,404		remote_head.created_at, strips))405	for mut clash in clashes {406		base := fetched_bytes(store, fetched, clash.base)!407		mine := fetched_bytes(store, fetched, clash.mine)!408		theirs := fetched_bytes(store, fetched, clash.theirs)!409		mine_delta := snapshot.diff_bytes(clash.path, 'modified', base, mine)!410		theirs_delta := snapshot.diff_bytes(clash.path, 'modified', base, theirs)!411		clash.mine_stat = delta_stat(mine_delta, clash.mine.size)412		clash.theirs_stat = delta_stat(theirs_delta, clash.theirs.size)413		clash.mine_patch = mine_delta.patch414		clash.theirs_patch = theirs_delta.patch415		clash.mine_save = last_touch(store, local_only, clash.path)!416		clash.theirs_save = last_touch(store, fetched.saves.map(to_save(it)), clash.path)!417	}418	return clashes419}420421fn delta_stat(delta snapshot.Delta, size i64) string {422	if delta.binary {423		return fmt.human_bytes(size)424	}425	return '+${delta.added} -${delta.removed}'426}427428fn last_touch(store &storage.Store, saves []history.Save, path string) !history.Save {429	for index := saves.len - 1; index >= 0; index-- {430		save := saves[index]431		current := snapshot.index_files(history.files_of(store, save.id)!)[path] or {432			snapshot.FileEntry{}433		}434		parent := if save.parent != '' {435			snapshot.index_files(history.files_of(store, save.parent)!)[path] or {436				snapshot.FileEntry{}437			}438		} else {439			snapshot.FileEntry{}440		}441		if !same(current, parent) {442			return save443		}444	}445	return saves.last()446}447448fn combine_preview(store &storage.Store, name string, fetched Fetched, local []history.Save, clashes []Clash, yes bool, all_side string) !StealPreview {449	base := history.files_of(store, fetched.base)!450	mine := history.files_of(store, local.last().id)!451	theirs := history.files_of(store, fetched.head)!452	mine_changed := changed_paths(base, mine)453	theirs_changed := changed_paths(base, theirs)454	mut changed := map[string]bool{}455	for path in mine_changed {456		changed[path] = true457	}458	for path in theirs_changed {459		changed[path] = true460	}461	mut identical := 0462	base_map := snapshot.index_files(base)463	mine_map := snapshot.index_files(mine)464	theirs_map := snapshot.index_files(theirs)465	for path, _ in changed {466		if !same(mine_map[path] or { snapshot.FileEntry{} }, base_map[path] or { snapshot.FileEntry{} })467			&& same(mine_map[path] or { snapshot.FileEntry{} }, theirs_map[path] or { snapshot.FileEntry{} }) {468			identical++469		}470	}471	return StealPreview{472		repo:      name473		base:      history.by_id(store, fetched.base) or { history.Save{} }474		local:     local475		remote:    fetched.saves476		changed:   changed.len477		automatic: changed.len - identical - clashes.len478		identical: identical479		clashes:   clashes480		yes:       yes481		all_side:  all_side482	}483}484485// after_strips is a save's file list once the given strip events are applied,486// by the same rule write_fetched uses.487fn after_strips(files []snapshot.FileEntry, save_id string, created_at i64, strips []events.Event) []snapshot.FileEntry {488	return files.filter(fn [strips, save_id, created_at] (file snapshot.FileEntry) bool {489		return !strips.any(reaches(it, save_id, created_at) && covers(it.path, file.path))490	})491}492493// fetched_bytes reads one side of a clash: from the fetch when it has just494// arrived, else from the store. An absent side is empty.495fn fetched_bytes(store &storage.Store, fetched Fetched, entry snapshot.FileEntry) ![]u8 {496	if entry.hash == '' {497		return []u8{}498	}499	if blob := fetched.repo_objects[entry.hash] {500		return zlib.decompress(blob)!501	}502	return store.get_object(entry.hash)!503}504505fn choose_sides(clashes []Clash, opts StealOptions) !map[string]Side {506	mut sides := map[string]Side{}507	if clashes.len == 0 {508		return sides509	}510	for clash in clashes {511		if opts.mine {512			sides[clash.path] = .mine513			continue514		}515		if opts.theirs {516			sides[clash.path] = .theirs517			continue518		}519		return ClashError{520			paths: clashes.map(it.path)521		}522	}523	return sides524}525526fn same(a snapshot.FileEntry, b snapshot.FileEntry) bool {527	if a.hash == '' && b.hash == '' {528		return true529	}530	return a.hash == b.hash && a.executable == b.executable531}532533fn changed_since(store &storage.Store, before ?history.Save, strips_before int) !bool {534	if events.strip_events(store)!.len != strips_before {535		return true536	}537	now := history.head(store)538	if now or { history.Save{} }.id != before or { history.Save{} }.id {539		return true540	}541	return dirty(store, now)!542}543544// dirty reports whether the working tree holds anything a steal would545// overwrite. With no saves yet, that is every file but the untouched ignore546// list `koh init` wrote.547pub fn dirty(store &storage.Store, head ?history.Save) !bool {548	files := snapshot.walk(store, store.root, snapshot.load(store.root))!549	if saved := head {550		return !snapshot.same_tree(history.files_of(store, saved.id)!, files)551	}552	seed := storage.hash_hex(snapshot.default_ignore.bytes())553	return files.any(it.path != snapshot.ignore_file || it.hash != seed)554}555556// fetch_repo pulls a whole repo — head, saves, objects and events — for557// `koh steal <name>`, which lands a copy in a new folder.558pub fn fetch_repo(mut backend remote.Backend, name string) !Fetched {559	check_format(mut backend, name)!560	remote_head := backend.get(head_key(name))!561	if !remote_head.found {562		return error('the remote has no repo called "${name}"')563	}564	save_ids := backend.list('${name}/saves')!565	object_keys := backend.list('${name}/objects')!566	event_keys := backend.list('${name}/events')!567	mut fetched := Fetched{568		head: remote_head.body.bytestr().trim_space()569	}570	for key in object_keys {571		blob := backend.get(key)!572		if blob.found {573			fetched.repo_objects[os.base(key)] = blob.body574		}575	}576	for key in save_ids {577		body := backend.get(key)!578		if !body.found {579			continue580		}581		record := decode_save(body.body)!582		fetched.saves << record583	}584	fetched.saves = parent_first(fetched.saves)!585	for key in event_keys {586		body := backend.get(key)!587		if body.found {588			fetched.events_out << decode_event(body.body)!589		}590	}591	return fetched592}593594// parent_first orders saves so every parent lands before its children, as the595// foreign key on `parent` demands. Time cannot do it: a replayed save keeps its596// original, older time but sits on a newer parent.597fn parent_first(records []SaveRecord) ![]SaveRecord {598	mut by_id := map[string]SaveRecord{}599	for record in records {600		by_id[record.id] = record601	}602	mut placed := map[string]bool{}603	mut ordered := []SaveRecord{}604	for record in records {605		mut chain := []SaveRecord{}606		mut cursor := record.id607		for cursor != '' && cursor !in placed {608			if chain.len > records.len {609				return error('the save records on the remote form a loop')610			}611			current := by_id[cursor] or { return error('the remote is missing save ${cursor}') }612			chain << current613			cursor = current.parent614		}615		chain.reverse_in_place()616		for current in chain {617			placed[current.id] = true618			ordered << current619		}620	}621	return ordered622}