git import: build a merge from the paths it can change ce118287d9da

A merge was built from its whole tree, rendering and comparing every
file: about 18 s for any merge at 118k commits of VS Code, 85% of the
import's time. A merge can differ from its first parent only at the
paths Git's diff names and where the merged changes touched, read in
the first parent's tree and in the merged state; with those it is built
like an ordinary commit. A tree conflict among what the merge touched
still takes the whole-tree path (OXY_IMPORT_WHOLE_MERGES=1 forces it,
for comparing). The trace says which path each merge took.

On the recovered VS Code copy small merges went from ~18 s to 13-139 ms;
large ones now cost what they rebuild (23-63 s for 43-308 files). Every
commit of four generated histories (210 merges, 29 conflicted)
reproduced by git verify. Not yet verified at VS Code depth: git verify
there ran out of memory beside the live import.

refs #80

Author: Andy McCall @andymccall <[email protected]>
When: 29 days ago · 2026-10-06 23:27 UTC
Signature: ✔ signed by Andy McCall
Hash: ce118287d9da03ef5c98345e3149109c48cf872b6813ec469ccdc2f269e6f34c
Depends on: 2306a4d24779 58dfe0e134eb 79ab8528ff62 810691ca6ce6 c3069537d7c5 c3d2ef6104c2 fb5b6181618a
Depended on by: d256e826ac5d 579afd107b9b
In bookmarks: bare-hashes carried-not-removed carry-identical doctor-trust identical-sides keyless-tags main merge-remote-bookmark only-help-103 paths-for-resolutions-and-amend push-notes show-stat subrepo-pin-state switch-says
In tags: v0.10.0 v0.11.0 v0.4.1 v0.4.2 v0.4.3 v0.4.4 v0.4.5 v0.4.6 v0.5.0 v0.5.1 v0.6.0 v0.7.0 v0.8.0 v0.9.0
Edits: 12 atoms, 0 tree operations, 1 file

Browse the tree at this change

hide whitespace changes

modified crates/oxy-core/src/repo/git.rs +69 −3

		…	932 unchanged lines
933	933		let stop_after: Option<usize> = std::env::var("OXY_IMPORT_STOP_AFTER")
934	934		.ok()
935	935		.and_then(\|v\| v.parse().ok());
	936	+	let whole_merges = std::env::var_os("OXY_IMPORT_WHOLE_MERGES").filter(\|v\| v != "0");
936	937		let total = commits.len();
937	938		for (index, gc) in commits.iter().enumerate() {
938	939		if known.imported.contains_key(&gc.sha) \|\| known.exported.contains_key(&gc.sha) {
		…	62 unchanged lines
1001	1002		// tree cannot vouch for them.
1002	1003		let mut touched: HashSet<NodeId> = HashSet::new();
1003	1004		let mut merged = 0usize;
	1005	+	// Where the first parent has each node, read before the merged
	1006	+	// changes move anything: a merge's partial build names the paths
	1007	+	// they touch in the first parent's tree as well as in the merged
	1008	+	// state (oxygen#80).
	1009	+	let mut first_parent_view: Option<crate::tree::TreeView> = None;
1004	1010		if gc.parents.len() > 1 {
1005	1011		report.merges += 1;
	1012	+	if prev_tree.is_some() && whole_merges.is_none() {
	1013	+	first_parent_view = Some(base.tree().view());
	1014	+	}
1006	1015		let mut args: Vec<String> = gc.parents[1..].to_vec();
1007	1016		args.push(format!("^{}", gc.parents[0]));
1008	1017		let refs: Vec<&str> = args.iter().map(String::as_str).collect();
		…	54 unchanged lines
1063	1072		// files that decide how they are stored, and the directories its
1064	1073		// removals may leave empty. A merge, or a commit whose parent's
1065	1074		// tree is not at hand, is built from its whole tree.
	1075	+	// A merge can differ from its first parent only at the paths
	1076	+	// Git's diff names and where the merged changes touched: those
	1077	+	// paths in the first parent's tree and in the merged state. With
	1078	+	// them added it is built like an ordinary commit, instead of
	1079	+	// from its whole tree (18 s for any merge at 118k commits of
	1080	+	// VS Code, oxygen#80). OXY_IMPORT_WHOLE_MERGES=1 restores the
	1081	+	// whole-tree path, for comparing.
	1082	+	let mut changed = changed;
	1083	+	// A tree conflict in the merged state (both sides placed a file
	1084	+	// at one path) is resolved by the whole-tree path.
	1085	+	let mut merge_how = if gc.parents.len() > 1 {
	1086	+	if first_parent_view.is_some() {
	1087	+	"partial"
	1088	+	} else {
	1089	+	"whole"
	1090	+	}
	1091	+	} else {
	1092	+	"-"
	1093	+	};
	1094	+	// Only a conflict among what the merged changes touched; one
	1095	+	// elsewhere stays as it was in the first parent either way.
	1096	+	if first_parent_view.is_some()
	1097	+	&& base.tree().view().conflicts.iter().any(\|c\| {
	1098	+	use crate::tree::TreeConflict::*;
	1099	+	match c {
	1100	+	Name { nodes, .. } => nodes.iter().any(\|n\| touched.contains(n)),
	1101	+	MultiPlacement { node, .. } \| Cycle { node } \| Mode { node, .. } => {
	1102	+	touched.contains(node)
	1103	+	}
	1104	+	Orphan { node, parent } => {
	1105	+	touched.contains(node) \|\| touched.contains(parent)
	1106	+	}
	1107	+	}
	1108	+	})
	1109	+	{
	1110	+	first_parent_view = None;
	1111	+	merge_how = "conflicted";
	1112	+	}
	1113	+	if let (Some(ch), Some(fp)) = (changed.as_mut(), &first_parent_view) {
	1114	+	let union = base.tree().view();
	1115	+	for v in [fp, &union] {
	1116	+	for (path, e) in v.entries.iter() {
	1117	+	if touched.contains(&e.node) {
	1118	+	ch.insert(path.clone());
	1119	+	}
	1120	+	}
	1121	+	}
	1122	+	}
1066	1123		let partial = changed.is_some()
1067		-	&& gc.parents.len() == 1
	1124	+	&& (gc.parents.len() == 1 \|\| first_parent_view.is_some())
1068	1125		&& !tree.values().any(\|(mode, _)\| mode == "160000");
1069	1126		let mut rel: BTreeSet<&str> = BTreeSet::new();
	1127	+	// Text files whose graphs this commit builds, for the trace.
	1128	+	let need_n: usize;
1070	1129		let base_snapshot = if let (true, Some(changed)) = (partial, &changed) {
1071	1130		let view = base.tree().view();
1072	1131		rel.extend(changed.iter().map(String::as_str));
		…	19 unchanged lines
1092	1151		.map(\|e\| e.node)
1093	1152		.collect();
1094	1153		crate::timing::add("render: same and need", clock.elapsed());
	1154	+	need_n = need.len();
1095	1155		let t = std::time::Instant::now();
1096	1156		self.load_graphs_of(&mut base, &need)?;
1097	1157		crate::timing::add("render: load graphs", t.elapsed());
		…	37 unchanged lines
1135	1195		.map(\|e\| e.node)
1136	1196		.collect();
1137	1197		crate::timing::add("render: same and need", clock.elapsed());
	1198	+	need_n = need.len();
1138	1199		let t = std::time::Instant::now();
1139	1200		let snap = if need.len() > merge_batch() {
1140	1201		// A merge onto a base with no built graphs: thousands
1141	1202		// of files, whose graphs would not fit at once.
1142	1203		self.materialize_batched(&mut base, &need, &skip)?
1143	1204		} else {
	1205	+	let g = std::time::Instant::now();
1144	1206		self.load_graphs_of(&mut base, &need)?;
1145		-	base.materialize_except(&skip)
	1207	+	crate::timing::add("render: whole, load graphs", g.elapsed());
	1208	+	let m = std::time::Instant::now();
	1209	+	let snap = base.materialize_except(&skip);
	1210	+	crate::timing::add("render: whole, materialize", m.elapsed());
	1211	+	snap
1146	1212		};
1147	1213		crate::timing::add("render: whole tree", t.elapsed());
1148	1214		snap
		…	227 unchanged lines
1376	1442		.map(\|(st, _)\| st.built_atoms())
1377	1443		.unwrap_or(0);
1378	1444		eprintln!(
1379		-	"trace {done} {} parents={} base={base_how} merged={merged} built={built} atoms={atoms} kept={} shed={shed} rss_mb={} before_trim_mb={before_trim} deferred_edits={edits} most={most} ms={}",
	1445	+	"trace {done} {} parents={} base={base_how} merged={merged} built={built} atoms={atoms} kept={} shed={shed} rss_mb={} before_trim_mb={before_trim} deferred_edits={edits} most={most} need={need_n} merge={merge_how} ms={}",
1380	1446		&gc.sha[..12.min(gc.sha.len())],
1381	1447		gc.parents.len(),
1382	1448		kept.len(),
		…	554 unchanged lines

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

git import: build a merge from the paths it can change ce118287d9da

Keyboard