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 blended line by line, it is chosen.89module exchange1011import compress.zlib12import src.apply13import src.events14import src.fmt15import src.history16import src.remote17import src.snapshot18import src.storage19import strconv2021pub 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	unsafe_paths  []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		unsafe_paths:    fetched.unsafe_paths124	}125	mut local_only := []history.Save{}126	if head := head_before {127		// The remote builds on `base`. If that save is here but no longer on128		// the line, neither line contains the other; jumping to the remote129		// would silently leave this line behind.130		local_only = saves_after(store, head.id, fetched.base) or {131			return error('the remote builds on save ${fetched.base}, which is not on this line — load the save you want, then offer')132		}133	}134	if fetched.base == '' && local_only.len > 0 {135		return error('the remote keeps a different history — it shares no save with this repo')136	}137	if fetched.saves.len > 0 {138		store.begin()!139		write_fetched_records(store, fetched) or {140			store.rollback()141			return err142		}143		store.end()!144	}145146	strips_before := events.strip_events(store)!.len147	mut clashes := []Clash{}148	mut side_of := map[string]Side{}149	if fetched.saves.len > 0 && local_only.len > 0 {150		clashes = combine_clashes(store, fetched, local_only)!151		report.clashes = clashes.map(it.path)152		if opts.guide != unsafe { nil } {153			side_of = opts.guide(combine_preview(store, name, fetched, local_only, clashes,154				opts.yes, if opts.mine {155					'mine'156				} else if opts.theirs { 'theirs' } else { '' })!)!157		} else {158			// Asked before the write lock: a person thinking must not stall every159			// agent's save on this repo.160			side_of = choose_sides(clashes, opts)!161		}162	}163	for clash in clashes {164		if side_of[clash.path] == .theirs {165			report.kept_versions << '${clash.path}:${local_only.last().id}'166		}167	}168169	store.begin() or { return err }170	// The questions ran without the lock. If a save or an edit landed171	// meanwhile, the answers were about a line that no longer exists.172	if moved := changed_since(store, head_before, strips_before) {173		if moved {174			store.rollback()175			return error('this repo changed while steal was asking — run koh steal again')176		}177	} else {178		store.rollback()179		return err180	}181	final := (write_and_combine(store, fetched, local_only, clashes, side_of, mut report) or {182		store.rollback()183		return err184	})185	files := history.files_of(store, final.id) or {186		store.rollback()187		return err188	}189	snapshot.check_links(store.root, files) or {190		store.rollback()191		return err192	}193	// The files follow the transaction; the mark lands with it, in one step.194	// No head before means a fresh steal, whose whole tree is new.195	moved := if head := head_before { final.id != head.id } else { true }196	if moved {197		snapshot.mark_restore(store) or {198			store.rollback()199			return err200		}201	}202	store.end() or { return err }203	report.head = final.id204	if local_only.len > 0 && report.fetched_saves > 0 {205		report.previous_head = local_only.last().id206	}207	flags := events.latest_flags(store)!208	for record in fetched.saves {209		if flag := flags[record.id] {210			if flag.flagged {211				report.flagged << flag212			}213		}214	}215216	if head := head_before {217		if final.id == head.id {218			// The line did not move, so neither does the working tree.219			return report220		}221		mut wanted := map[string]bool{}222		for file in files {223			wanted[file.path] = true224		}225		mut remove := []string{}226		for file in history.files_of(store, head.id)! {227			if file.path !in wanted {228				remove << file.path229			}230		}231		result := snapshot.restore_files(store, store.root, snapshot.load(store.root), files,232			remove)!233		report.removed = result.removed234	} else {235		snapshot.restore_files(store, store.root, snapshot.load(store.root), files, [])!236	}237	history.refresh_log_md(store)238	return report239}240241// write_and_combine lands a fetch and, when the local line has saves the remote242// lacks, replays them on top of the remote head. It runs inside the caller's243// transaction and returns the new head.244fn write_and_combine(store &storage.Store, fetched Fetched, local_only []history.Save, clashes []Clash, side_of map[string]Side, mut report StealReport) !history.Save {245	write_fetched(store, fetched)!246	if fetched.saves.len == 0 {247		// The remote head is already on this line: level, or this machine is248		// ahead and the offer that follows a steal sends the rest.249		return history.head(store) or { return error('this repo has no head') }250	}251	if local_only.len == 0 {252		// Nothing of ours is missing from the remote: the line simply moves on.253		history.set_head(store, fetched.head)!254		report.forward = true255		return history.head(store) or { return error('the remote head did not land') }256	}257	remote_files := history.files_of(store, fetched.head)!258	mut mine_files := []snapshot.FileEntry{}259	if our_head := history.head(store) {260		mine_files = history.files_of(store, our_head.id)!261	}262263	// A file the remote changed is a clash, decided below, or one this machine264	// left as it was or changed the same way, so the remote's version stands.265	// Replaying this machine's steps on it could only conflict: an edit it266	// later undid would no longer apply.267	base_files := history.files_of(store, fetched.base)!268	settled := changed_paths(base_files, remote_files)269270	// Take the remote's line first, so the replayed saves chain onto it.271	history.set_head(store, fetched.head)!272	mut current := remote_files.clone()273	for save in local_only {274		parent_files := if save.parent != '' {275			history.files_of(store, save.parent)!276		} else {277			[]snapshot.FileEntry{}278		}279		target_files := history.files_of(store, save.id)!280		plan := apply.three_way(current, parent_files, target_files, [], settled)281		if apply.conflicts(plan) {282			return error('combine could not apply ${plan.conflict} — it is not a clash file')283		}284		if plan.applied.len == 0 {285			// Everything this save touched was a file the remote changed.286			continue287		}288		history.record_save(store, '', plan.files, history.SaveInput{289			message:       save.message290			created_at:    save.created_at291			machine:       save.machine292			agent:         save.agent293			session:       save.session294			is_checkpoint: save.is_checkpoint295			replayed_from: save.id296		})!297		current = plan.files.clone()298		report.replayed++299	}300301	mut mine_paths := []string{}302	for clash in clashes {303		if side_of[clash.path] == .mine {304			mine_paths << clash.path305		}306	}307	if mine_paths.len > 0 {308		// One last save puts my versions of the chosen files back.309		final_plan := apply.three_way(current, current, mine_files, mine_paths, [])310		if final_plan.applied.len > 0 {311			history.record_save(store, '', final_plan.files, history.SaveInput{312				message: 'combine: kept mine for ${mine_paths.len} ${if mine_paths.len == 1 {313					'file'314				} else {315					'files'316				}}'317			})!318			report.kept_mine = mine_paths.len319		}320	}321	return history.head(store) or { return error('the combined line has no head') }322}323324// find_clashes lists the files both sides changed, differently. Files changed325// identically on both sides are not clashes: there is nothing to decide.326pub fn find_clashes(base []snapshot.FileEntry, mine []snapshot.FileEntry, theirs []snapshot.FileEntry) []Clash {327	base_map := snapshot.index_files(base)328	mine_map := snapshot.index_files(mine)329	theirs_map := snapshot.index_files(theirs)330	mut paths := mine_map.keys()331	for path in theirs_map.keys() {332		if path !in mine_map {333			paths << path334		}335	}336	paths.sort()337	mut clashes := []Clash{}338	for path in paths {339		here := mine_map[path] or {340			snapshot.FileEntry{341				path: path342			}343		}344		there := theirs_map[path] or {345			snapshot.FileEntry{346				path: path347			}348		}349		was := base_map[path] or {350			snapshot.FileEntry{351				path: path352			}353		}354		if same(here, there) {355			continue356		}357		if same(here, was) || same(there, was) {358			continue359		}360		clashes << Clash{361			path:   path362			mine:   here363			theirs: there364			base:   was365		}366	}367	return clashes368}369370// changed_paths lists the paths whose entry differs between two trees.371fn changed_paths(before []snapshot.FileEntry, after []snapshot.FileEntry) []string {372	was := snapshot.index_files(before)373	now := snapshot.index_files(after)374	mut paths := []string{}375	for path, entry in now {376		if !same(entry, was[path] or { snapshot.FileEntry{} }) {377			paths << path378		}379	}380	for path, _ in was {381		if path !in now {382			paths << path383		}384	}385	return paths386}387388// combine_clashes finds the files both lines changed, with the diff stat each389// prompt shows. It reads the remote head from the fetch, not the store, so it390// can run before anything is written.391fn combine_clashes(store &storage.Store, fetched Fetched, local_only []history.Save) ![]Clash {392	base_files := if fetched.base != '' {393		history.files_of(store, fetched.base)!394	} else {395		[]snapshot.FileEntry{}396	}397	head := history.head(store) or { return []Clash{} }398	// The transaction applies every known strip before it replays, so the399	// clashes are found on the trees as they will be then, or the answers400	// would be about files that are no longer there.401	strips := known_strips(store, fetched)!402	remote_head := fetched.saves.last()403	mut clashes := find_clashes(after_strips(base_files, fetched.base, strips), after_strips(history.files_of(store,404		head.id)!, head.id, strips), after_strips(to_files(remote_head), remote_head.id, 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}447448// combine_preview counts what a combine would do to the paths either side changed since `base`:449// `identical` were changed the same way on both sides, `clashes` need a choice, the rest go in by themselves.450fn combine_preview(store &storage.Store, name string, fetched Fetched, local []history.Save, clashes []Clash, yes bool, all_side string) !StealPreview {451	base := history.files_of(store, fetched.base)!452	mine := history.files_of(store, local.last().id)!453	theirs := history.files_of(store, fetched.head)!454	mine_changed := changed_paths(base, mine)455	theirs_changed := changed_paths(base, theirs)456	mut changed := map[string]bool{}457	for path in mine_changed {458		changed[path] = true459	}460	for path in theirs_changed {461		changed[path] = true462	}463	mut identical := 0464	base_map := snapshot.index_files(base)465	mine_map := snapshot.index_files(mine)466	theirs_map := snapshot.index_files(theirs)467	for path, _ in changed {468		if !same(mine_map[path] or { snapshot.FileEntry{} }, base_map[path] or { snapshot.FileEntry{} })469			&& same(mine_map[path] or { snapshot.FileEntry{} }, theirs_map[path] or { snapshot.FileEntry{} }) {470			identical++471		}472	}473	return StealPreview{474		repo:      name475		base:      history.by_id(store, fetched.base) or { history.Save{} }476		local:     local477		remote:    fetched.saves478		changed:   changed.len479		automatic: changed.len - identical - clashes.len480		identical: identical481		clashes:   clashes482		yes:       yes483		all_side:  all_side484	}485}486487// after_strips is a save's file list once the given strip events are applied,488// by the same rule write_fetched uses.489fn after_strips(files []snapshot.FileEntry, save_id string, strips []events.Event) []snapshot.FileEntry {490	return files.filter(fn [strips, save_id] (file snapshot.FileEntry) bool {491		return !strips.any(reaches(it, save_id) && covers(it.path, file.path))492	})493}494495// fetched_bytes reads one side of a clash: from the fetch when it has just496// arrived, else from the store. An absent side is empty.497fn fetched_bytes(store &storage.Store, fetched Fetched, entry snapshot.FileEntry) ![]u8 {498	if entry.hash == '' {499		return []u8{}500	}501	if blob := fetched.repo_objects[entry.hash] {502		return zlib.decompress(blob)!503	}504	return store.get_object(entry.hash)!505}506507fn choose_sides(clashes []Clash, opts StealOptions) !map[string]Side {508	mut sides := map[string]Side{}509	if clashes.len == 0 {510		return sides511	}512	for clash in clashes {513		if opts.mine {514			sides[clash.path] = .mine515			continue516		}517		if opts.theirs {518			sides[clash.path] = .theirs519			continue520		}521		return ClashError{522			paths: clashes.map(it.path)523		}524	}525	return sides526}527528fn same(a snapshot.FileEntry, b snapshot.FileEntry) bool {529	if a.hash == '' && b.hash == '' {530		return true531	}532	return a.hash == b.hash && a.executable == b.executable533}534535fn changed_since(store &storage.Store, before ?history.Save, strips_before int) !bool {536	if events.strip_events(store)!.len != strips_before {537		return true538	}539	now := history.head(store)540	if now or { history.Save{} }.id != before or { history.Save{} }.id {541		return true542	}543	return dirty(store, now)!544}545546// dirty reports whether the working tree holds anything a steal would547// overwrite. With no saves yet, that is every file but the untouched ignore548// list `koh init` wrote.549pub fn dirty(store &storage.Store, head ?history.Save) !bool {550	files := snapshot.walk(store, store.root, snapshot.load(store.root))!551	if saved := head {552		return !snapshot.same_tree(history.files_of(store, saved.id)!, files)553	}554	seed := storage.hash_hex(snapshot.default_ignore.bytes())555	return files.any(it.path != snapshot.ignore_file || it.hash != seed)556}557558// fetch_repo takes a whole repo — head, saves, objects and events — for559// `koh steal <name>`, which lands a copy in a new folder.560pub fn fetch_repo(mut backend remote.Backend, name string) !Fetched {561	check_format(mut backend, name)!562	remote_head := backend.get(head_key(name))!563	if !remote_head.found {564		return error('the remote has no repo called "${name}"')565	}566	mut fetched := Fetched{567		head: remote_head.body.bytestr().trim_space()568	}569	bundle := backend.get(bundle_key(name))!570	if bundle.found {571		take_bundle(mut fetched, bundle.body)!572	} else {573		for kind in ['objects', 'saves', 'events'] {574			for key in backend.list('${name}/${kind}')! {575				body := backend.get(key)!576				if body.found {577					take(mut fetched, key.all_after('${name}/'), body.body)!578				}579			}580		}581	}582	fetched.saves = parent_first(fetched.saves)!583	fetched.events_out.sort(a.id < b.id)584	return fetched585}586587// take_bundle splits §22.7's bundle — `<key> <length>\n` and then that many bytes, over and over,588// until `end 0` — into what one GET of each key would have returned. A connection that drops589// between two entries still looks like a whole bundle, so only the end line proves it arrived.590fn take_bundle(mut fetched Fetched, body []u8) ! {591	mut at := 0592	for at < body.len {593		// Scanned in place: a slice of `body` copies the rest of it, and that per entry is quadratic.594		mut newline := at595		for newline < body.len && body[newline] != `\n` {596			newline++597		}598		if newline == body.len {599			return error('the bundle ends part way through an entry')600		}601		header := body[at..newline].bytestr()602		if header == 'end 0' && newline + 1 == body.len {603			return604		}605		length := strconv.atoi(header.all_after(' '))!606		start := newline + 1607		if length < 0 || length > body.len - start {608			return error('the bundle ends part way through ${header.all_before(' ')}')609		}610		take(mut fetched, header.all_before(' '), body[start..start + length])!611		at = start + length612	}613	return error('the bundle was cut short — try the steal again')614}615616// take files one fetched key, relative to the repo: an object, a save or an event.617fn take(mut fetched Fetched, key string, body []u8) ! {618	match key.all_before('/') {619		'objects' {620			fetched.repo_objects[key.all_after('/')] = body621		}622		'saves' {623			mut record := decode_save(body)!624			fetched.unsafe_paths << drop_unsafe_paths(mut record)625			fetched.saves << record626		}627		'events' {628			event := decode_event(body)!629			if !ignored_strip(event) {630				fetched.events_out << event631			}632		}633		else {634			return error('the remote sent "${key}", which is not part of a repo')635		}636	}637}638639// parent_first orders saves so every parent lands before its children, as the640// foreign key on `parent` demands. Time cannot do it: a replayed save keeps its641// original, older time but sits on a newer parent.642fn parent_first(records []SaveRecord) ![]SaveRecord {643	mut by_id := map[string]SaveRecord{}644	for record in records {645		by_id[record.id] = record646	}647	mut placed := map[string]bool{}648	mut ordered := []SaveRecord{}649	for record in records {650		mut chain := []SaveRecord{}651		mut cursor := record.id652		for cursor != '' && cursor !in placed {653			if chain.len > records.len {654				return error('the save records on the remote form a loop')655			}656			current := by_id[cursor] or { return error('the remote is missing save ${cursor}') }657			chain << current658			cursor = current.parent659		}660		chain.reverse_in_place()661		for current in chain {662			placed[current.id] = true663			ordered << current664		}665	}666	return ordered667}