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	mine_stat    string34	theirs_stat  string35	mine_patch   string36	theirs_patch string37}3839pub struct StealPreview {40pub:41	repo      string42	base      string43	local     []history.Save44	remote    []SaveRecord45	changed   int46	automatic int47	identical int48	clashes   []Clash49	yes       bool50}5152pub struct StealOptions {53pub mut:54	mine   bool // resolve every clash as mine55	theirs bool // resolve every clash as theirs56	// Asked once per clash when neither flag is set. Nil means "nobody to ask".57	ask   fn (clash Clash) Side                      = unsafe { nil }58	guide fn (preview StealPreview) !map[string]Side = unsafe { nil }59	yes   bool60}6162pub struct StealReport {63pub mut:64	repo            string65	forward         bool66	fetched_saves   int67	fetched_objects int68	fetched_events  int69	clashes         []string70	kept_mine       int71	replayed        int72	removed         int73	head            string74	flagged         []events.Flag // incoming saves that are flagged75	// Set when a combine took this machine's saves off the line: loading it76	// brings back the tree from before the steal, less anything stripped.77	previous_head string78	kept_versions []string79}8081pub const dirty_tree = 'save or checkpoint first — steal needs a clean tree'82pub const no_saves_here = 'this folder has files but no saves — steal a repo into an empty folder with "koh steal <name>"'8384// steal brings the remote's new saves in. Inside a repo with its own work this85// may have to combine; a repo with nothing of its own simply fast-forwards.86pub fn steal(store &storage.Store, mut backend remote.Backend, opts StealOptions) !StealReport {87	name := repo_name(store, mut backend)!88	if snapshot.restore_pending(store) {89		return error(snapshot.restore_unfinished)90	}91	head_before := history.head(store)92	// Combining rewrites the working tree, so unsaved work would be lost.93	if dirty(store, head_before)! {94		if head_before == none {95			return error(no_saves_here)96		}97		return error(dirty_tree)98	}99	fetched := fetch_back_to_known(store, mut backend, name)!100	mut report := StealReport{101		repo:            name102		fetched_saves:   fetched.saves.len103		fetched_objects: fetched.repo_objects.len104		fetched_events:  fetched.events_out.len105		head:            fetched.head106	}107	mut local_only := []history.Save{}108	if head := head_before {109		// The remote builds on `base`. If that save is here but no longer on110		// the line, neither line contains the other; jumping to the remote111		// would silently leave this line behind.112		local_only = saves_after(store, head.id, fetched.base) or {113			return error('the remote builds on save ${fetched.base}, which is not on this line — load the save you want, then offer')114		}115	}116	if fetched.base == '' && local_only.len > 0 {117		return error('the remote keeps a different history — it shares no save with this repo')118	}119120	strips_before := events.strip_events(store)!.len121	mut clashes := []Clash{}122	mut side_of := map[string]Side{}123	if fetched.saves.len > 0 && local_only.len > 0 {124		clashes = combine_clashes(store, fetched)!125		report.clashes = clashes.map(it.path)126		if opts.guide != unsafe { nil } && !opts.mine && !opts.theirs {127			side_of = opts.guide(combine_preview(store, name, fetched, local_only, clashes,128				opts.yes)!)!129		} else {130			// Asked before the write lock: a person thinking must not stall every131			// agent's save on this repo.132			side_of = choose_sides(clashes, opts)!133		}134	}135	for clash in clashes {136		if side_of[clash.path] == .theirs {137			report.kept_versions << '${clash.path}:${local_only.last().id}'138		}139	}140141	store.begin() or { return err }142	// The questions ran without the lock. If a save or an edit landed143	// meanwhile, the answers were about a line that no longer exists.144	if moved := changed_since(store, head_before, strips_before) {145		if moved {146			store.rollback()147			return error('this repo changed while steal was asking — run koh steal again')148		}149	} else {150		store.rollback()151		return err152	}153	final := (write_and_combine(store, fetched, local_only, clashes, side_of, mut report) or {154		store.rollback()155		return err156	})157	files := history.files_of(store, final.id) or {158		store.rollback()159		return err160	}161	snapshot.check_links(store.root, files) or {162		store.rollback()163		return err164	}165	// The files follow the commit; the mark lands with it, in one step.166	// No head before means a fresh clone, whose whole tree is new.167	moved := if head := head_before { final.id != head.id } else { true }168	if moved {169		snapshot.mark_restore(store) or {170			store.rollback()171			return err172		}173	}174	store.commit() or { return err }175	report.head = final.id176	if local_only.len > 0 && report.fetched_saves > 0 {177		report.previous_head = local_only.last().id178	}179	flags := events.latest_flags(store)!180	for record in fetched.saves {181		if flag := flags[record.id] {182			if flag.flagged {183				report.flagged << flag184			}185		}186	}187188	if head := head_before {189		if final.id == head.id {190			// The line did not move, so neither does the working tree.191			return report192		}193		mut wanted := map[string]bool{}194		for file in files {195			wanted[file.path] = true196		}197		mut remove := []string{}198		for file in history.files_of(store, head.id)! {199			if file.path !in wanted {200				remove << file.path201			}202		}203		result := snapshot.restore_files(store, store.root, snapshot.load(store.root), files,204			remove)!205		report.removed = result.removed206	} else {207		snapshot.restore_files(store, store.root, snapshot.load(store.root), files, [])!208	}209	history.refresh_log_md(store)210	return report211}212213// write_and_combine lands a fetch and, when the local line has saves the remote214// lacks, replays them on top of the remote head. It runs inside the caller's215// transaction and returns the new head.216fn write_and_combine(store &storage.Store, fetched Fetched, local_only []history.Save, clashes []Clash, side_of map[string]Side, mut report StealReport) !history.Save {217	write_fetched(store, fetched)!218	if fetched.saves.len == 0 {219		// The remote head is already on this line: level, or this machine is220		// ahead and the offer that follows a steal sends the rest.221		return history.head(store) or { return error('this repo has no head') }222	}223	if local_only.len == 0 {224		// Nothing of ours is missing from the remote: the line simply moves on.225		history.set_head(store, fetched.head)!226		report.forward = true227		return history.head(store) or { return error('the remote head did not land') }228	}229	remote_files := history.files_of(store, fetched.head)!230	mut mine_files := []snapshot.FileEntry{}231	if our_head := history.head(store) {232		mine_files = history.files_of(store, our_head.id)!233	}234235	// A file the remote changed is a clash, decided below, or one this machine236	// left as it was or changed the same way, so the remote's version stands.237	// Replaying this machine's steps on it could only conflict: an edit it238	// later undid would no longer apply.239	base_files := history.files_of(store, fetched.base)!240	settled := changed_paths(base_files, remote_files)241242	// Take the remote's line first, so the replayed saves chain onto it.243	history.set_head(store, fetched.head)!244	mut current := remote_files.clone()245	for save in local_only {246		parent_files := if save.parent != '' {247			history.files_of(store, save.parent)!248		} else {249			[]snapshot.FileEntry{}250		}251		target_files := history.files_of(store, save.id)!252		plan := apply.three_way(current, parent_files, target_files, [], settled)253		if apply.conflicts(plan) {254			return error('combine could not apply ${plan.conflict} — it is not a clash file')255		}256		if plan.applied.len == 0 {257			// Everything this save touched was a file the remote changed.258			continue259		}260		history.record_save(store, '', plan.files, history.SaveInput{261			message:       save.message262			created_at:    save.created_at263			machine:       save.machine264			agent:         save.agent265			session:       save.session266			is_checkpoint: save.is_checkpoint267			replayed_from: save.id268		})!269		current = plan.files.clone()270		report.replayed++271	}272273	mut mine_paths := []string{}274	for clash in clashes {275		if side_of[clash.path] == .mine {276			mine_paths << clash.path277		}278	}279	if mine_paths.len > 0 {280		// One last save puts my versions of the chosen files back.281		final_plan := apply.three_way(current, current, mine_files, mine_paths, [])282		if final_plan.applied.len > 0 {283			history.record_save(store, '', final_plan.files, history.SaveInput{284				message: 'combine: kept mine for ${mine_paths.len} ${if mine_paths.len == 1 {285					'file'286				} else {287					'files'288				}}'289			})!290			report.kept_mine = mine_paths.len291		}292	}293	return history.head(store) or { return error('the combined line has no head') }294}295296// find_clashes lists the files both sides changed, differently. Files changed297// identically on both sides are not clashes: there is nothing to decide.298pub fn find_clashes(base []snapshot.FileEntry, mine []snapshot.FileEntry, theirs []snapshot.FileEntry) []Clash {299	base_map := snapshot.index_files(base)300	mine_map := snapshot.index_files(mine)301	theirs_map := snapshot.index_files(theirs)302	mut paths := mine_map.keys()303	for path in theirs_map.keys() {304		if path !in mine_map {305			paths << path306		}307	}308	paths.sort()309	mut clashes := []Clash{}310	for path in paths {311		here := mine_map[path] or {312			snapshot.FileEntry{313				path: path314			}315		}316		there := theirs_map[path] or {317			snapshot.FileEntry{318				path: path319			}320		}321		was := base_map[path] or {322			snapshot.FileEntry{323				path: path324			}325		}326		if same(here, there) {327			continue328		}329		if same(here, was) || same(there, was) {330			continue331		}332		clashes << Clash{333			path:   path334			mine:   here335			theirs: there336			base:   was337		}338	}339	return clashes340}341342// changed_paths lists the paths whose entry differs between two trees.343fn changed_paths(before []snapshot.FileEntry, after []snapshot.FileEntry) []string {344	was := snapshot.index_files(before)345	now := snapshot.index_files(after)346	mut paths := []string{}347	for path, entry in now {348		if !same(entry, was[path] or { snapshot.FileEntry{} }) {349			paths << path350		}351	}352	for path, _ in was {353		if path !in now {354			paths << path355		}356	}357	return paths358}359360// combine_clashes finds the files both lines changed, with the diff stat each361// prompt shows. It reads the remote head from the fetch, not the store, so it362// can run before anything is written.363fn combine_clashes(store &storage.Store, fetched Fetched) ![]Clash {364	base_files := if fetched.base != '' {365		history.files_of(store, fetched.base)!366	} else {367		[]snapshot.FileEntry{}368	}369	head := history.head(store) or { return []Clash{} }370	// The transaction applies the incoming strips before it replays, so the371	// clashes are found on the trees as they will be then, or the answers372	// would be about files that are no longer there.373	strips := fetched.events_out.filter(it.kind == events.kind_strip)374	// Base and mine are here already, so every strip reaches them (created 0).375	remote_head := fetched.saves.last()376	mut clashes := find_clashes(after_strips(base_files, fetched.base, 0, strips), after_strips(history.files_of(store,377		head.id)!, head.id, 0, strips), after_strips(to_files(remote_head), remote_head.id,378		remote_head.created_at, strips))379	for mut clash in clashes {380		base := fetched_bytes(store, fetched, clash.base)!381		mine := fetched_bytes(store, fetched, clash.mine)!382		theirs := fetched_bytes(store, fetched, clash.theirs)!383		mine_delta := snapshot.diff_bytes(clash.path, 'modified', base, mine)!384		theirs_delta := snapshot.diff_bytes(clash.path, 'modified', base, theirs)!385		clash.mine_stat = delta_stat(mine_delta)386		clash.theirs_stat = delta_stat(theirs_delta)387		clash.mine_patch = mine_delta.patch388		clash.theirs_patch = theirs_delta.patch389	}390	return clashes391}392393fn delta_stat(delta snapshot.Delta) string {394	if delta.binary {395		return 'binary'396	}397	return '+${delta.added} -${delta.removed}'398}399400fn combine_preview(store &storage.Store, name string, fetched Fetched, local []history.Save, clashes []Clash, yes bool) !StealPreview {401	base := history.files_of(store, fetched.base)!402	mine := history.files_of(store, local.last().id)!403	theirs := history.files_of(store, fetched.head)!404	mine_changed := changed_paths(base, mine)405	theirs_changed := changed_paths(base, theirs)406	mut changed := map[string]bool{}407	for path in mine_changed {408		changed[path] = true409	}410	for path in theirs_changed {411		changed[path] = true412	}413	mut identical := 0414	base_map := snapshot.index_files(base)415	mine_map := snapshot.index_files(mine)416	theirs_map := snapshot.index_files(theirs)417	for path, _ in changed {418		if !same(mine_map[path] or { snapshot.FileEntry{} }, base_map[path] or { snapshot.FileEntry{} })419			&& same(mine_map[path] or { snapshot.FileEntry{} }, theirs_map[path] or { snapshot.FileEntry{} }) {420			identical++421		}422	}423	return StealPreview{424		repo:      name425		base:      fetched.base426		local:     local427		remote:    fetched.saves428		changed:   changed.len429		automatic: changed.len - identical - clashes.len430		identical: identical431		clashes:   clashes432		yes:       yes433	}434}435436// after_strips is a save's file list once the given strip events are applied,437// by the same rule write_fetched uses.438fn after_strips(files []snapshot.FileEntry, save_id string, created_at i64, strips []events.Event) []snapshot.FileEntry {439	return files.filter(fn [strips, save_id, created_at] (file snapshot.FileEntry) bool {440		return !strips.any(reaches(it, save_id, created_at) && covers(it.path, file.path))441	})442}443444// fetched_bytes reads one side of a clash: from the fetch when it has just445// arrived, else from the store. An absent side is empty.446fn fetched_bytes(store &storage.Store, fetched Fetched, entry snapshot.FileEntry) ![]u8 {447	if entry.hash == '' {448		return []u8{}449	}450	if blob := fetched.repo_objects[entry.hash] {451		return zlib.decompress(blob)!452	}453	return store.get_object(entry.hash)!454}455456fn choose_sides(clashes []Clash, opts StealOptions) !map[string]Side {457	mut sides := map[string]Side{}458	if clashes.len == 0 {459		return sides460	}461	for clash in clashes {462		if opts.mine {463			sides[clash.path] = .mine464			continue465		}466		if opts.theirs {467			sides[clash.path] = .theirs468			continue469		}470		if opts.ask != unsafe { nil } {471			sides[clash.path] = opts.ask(clash)472			continue473		}474		paths := clashes.map(it.path).join(', ')475		return error('${paths} changed on both machines — run on a terminal to choose, or pass --mine or --theirs')476	}477	return sides478}479480fn same(a snapshot.FileEntry, b snapshot.FileEntry) bool {481	if a.hash == '' && b.hash == '' {482		return true483	}484	return a.hash == b.hash && a.executable == b.executable485}486487fn changed_since(store &storage.Store, before ?history.Save, strips_before int) !bool {488	if events.strip_events(store)!.len != strips_before {489		return true490	}491	now := history.head(store)492	if now or { history.Save{} }.id != before or { history.Save{} }.id {493		return true494	}495	return dirty(store, now)!496}497498// dirty reports whether the working tree holds anything a steal would499// overwrite. With no saves yet, that is every file but the untouched ignore500// list `koh init` wrote.501pub fn dirty(store &storage.Store, head ?history.Save) !bool {502	files := snapshot.walk(store, store.root, snapshot.load(store.root))!503	if saved := head {504		return !snapshot.same_tree(history.files_of(store, saved.id)!, files)505	}506	seed := storage.hash_hex(snapshot.default_ignore.bytes())507	return files.any(it.path != snapshot.ignore_file || it.hash != seed)508}509510// fetch_repo pulls a whole repo — head, saves, objects and events — for511// `koh steal <name>`, which lands a copy in a new folder.512pub fn fetch_repo(mut backend remote.Backend, name string) !Fetched {513	check_format(mut backend, name)!514	remote_head := backend.get(head_key(name))!515	if !remote_head.found {516		return error('the remote has no repo called "${name}"')517	}518	save_ids := backend.list('${name}/saves')!519	object_keys := backend.list('${name}/objects')!520	event_keys := backend.list('${name}/events')!521	mut fetched := Fetched{522		head: remote_head.body.bytestr().trim_space()523	}524	for key in object_keys {525		blob := backend.get(key)!526		if blob.found {527			fetched.repo_objects[os.base(key)] = blob.body528		}529	}530	for key in save_ids {531		body := backend.get(key)!532		if !body.found {533			continue534		}535		record := decode_save(body.body)!536		fetched.saves << record537	}538	fetched.saves = parent_first(fetched.saves)!539	for key in event_keys {540		body := backend.get(key)!541		if body.found {542			fetched.events_out << decode_event(body.body)!543		}544	}545	return fetched546}547548// parent_first orders saves so every parent lands before its children, as the549// foreign key on `parent` demands. Time cannot do it: a replayed save keeps its550// original, older time but sits on a newer parent.551fn parent_first(records []SaveRecord) ![]SaveRecord {552	mut by_id := map[string]SaveRecord{}553	for record in records {554		by_id[record.id] = record555	}556	mut placed := map[string]bool{}557	mut ordered := []SaveRecord{}558	for record in records {559		mut chain := []SaveRecord{}560		mut cursor := record.id561		for cursor != '' && cursor !in placed {562			if chain.len > records.len {563				return error('the save records on the remote form a loop')564			}565			current := by_id[cursor] or { return error('the remote is missing save ${cursor}') }566			chain << current567			cursor = current.parent568		}569		chain.reverse_in_place()570		for current in chain {571			placed[current.id] = true572			ordered << current573		}574	}575	return ordered576}