A state index for the working copy's base f9575918477f

Each workspace keeps its working copy's base as a local state index
(oxygen#41): the change metadata, tree and tree view, replace records,
and every file's deferred history with its graph key, in a flat binary
layout whose tree, view and histories decode side by side. A snapshot
reads it instead of replaying history when every dependency it asks for
is in it and their heads are its heads; otherwise it loads history and
writes the index for next time. It is derived only: the same state
whatever order history was read in, and a test build checks every read
against a full load.

The tree's own maps use the fast hasher, and a node's placements and
modes (nearly always one) are held without an allocation. Deferred
entries keep their graph key once worked out.

On the Linux tip the base now loads in 0.22 to 0.24 s rather than 1.0 s
(history 0.70 s, tree view 0.31 s); a one-file status is about 1.9 s.

refs #41

Author: Andy McCall @andymccall <[email protected]>
When: 1 month ago · 2026-09-30 10:15 UTC
Signature: ✔ signed by Andy McCall
Hash: f9575918477f3f804d14bddb1e3d4ef61067c4697531d5238942a87c4b227f3a
Depends on: 0bdc3f91a39f 2306a4d24779 252e8cb23fbc 75167672ebcd 86e1824f2d0b 982864068a59 a4fad5b085c7 cc7a00565161 cdb5beba7f05 e83354cdac22 e8d38e47e9d7 f6451fbbae3f ff0af1ee299d
Depended on by: c2e1d09047db 74b4a3c62ea4 bf0247ee3590 ac03130a2b95 5552e69c7325 79b5a90ffd43 d45dab0484ea fddf64baa3d2 fb5b6181618a 638fb21420d7 f9466021286a ce14f0d68b15 4cce912a0953 36e51aa806c6 3f1b8fe25ec9 05059d434aca
In bookmarks: agents-in-readme 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.1.0 v0.10.0 v0.11.0 v0.2.0 v0.3.0 v0.3.1 v0.4.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: 24 atoms, 1 tree operation, 6 files

Browse the tree at this change

hide whitespace changes

added crates/oxy-core/src/flat.rs +137 −0

modified crates/oxy-core/src/lib.rs +1 −0

modified crates/oxy-core/src/repo/mod.rs +67 −0

modified crates/oxy-core/src/repo/snapshot.rs +1 −1

modified crates/oxy-core/src/state.rs +330 −4

modified crates/oxy-core/src/tree.rs +275 −13

1	+	//! A flat binary layout for local indexes (oxygen#41): fixed-width
2	+	//! little-endian numbers and length-prefixed bytes, read in one pass
3	+	//! without building a generic value tree. Only for caches this repository
4	+	//! derives and can derive again: never exchanged, never trusted beyond the
5	+	//! key they are stored under, and a reader that finds anything amiss fails
6	+	//! so the caller rebuilds.
7	+
8	+	use crate::hash::ObjectRef;
9	+	use crate::objects::ObjectError;
10	+
11	+	#[derive(Default)]
12	+	pub struct Writer(pub Vec<u8>);
13	+
14	+	impl Writer {
15	+	pub fn u8(&mut self, v: u8) {
16	+	self.0.push(v);
17	+	}
18	+	pub fn u32(&mut self, v: u32) {
19	+	self.0.extend_from_slice(&v.to_le_bytes());
20	+	}
21	+	pub fn u64(&mut self, v: u64) {
22	+	self.0.extend_from_slice(&v.to_le_bytes());
23	+	}
24	+	/// A count, which must fit in 32 bits.
25	+	pub fn count(&mut self, n: usize) {
26	+	self.u32(u32::try_from(n).expect("an index count fits in 32 bits"));
27	+	}
28	+	pub fn fixed(&mut self, b: &[u8]) {
29	+	self.0.extend_from_slice(b);
30	+	}
31	+	pub fn bytes(&mut self, b: &[u8]) {
32	+	self.count(b.len());
33	+	self.0.extend_from_slice(b);
34	+	}
35	+	pub fn object(&mut self, r: &ObjectRef) {
36	+	self.fixed(&r.0);
37	+	}
38	+	pub fn opt_object(&mut self, r: &Option<ObjectRef>) {
39	+	match r {
40	+	None => self.u8(0),
41	+	Some(r) => {
42	+	self.u8(1);
43	+	self.object(r);
44	+	}
45	+	}
46	+	}
47	+	}
48	+
49	+	pub struct Reader<'a> {
50	+	buf: &'a [u8],
51	+	pos: usize,
52	+	}
53	+
54	+	fn short() -> ObjectError {
55	+	ObjectError::Schema("index: truncated".into())
56	+	}
57	+
58	+	impl<'a> Reader<'a> {
59	+	pub fn new(buf: &'a [u8]) -> Reader<'a> {
60	+	Reader { buf, pos: 0 }
61	+	}
62	+	pub fn at_end(&self) -> bool {
63	+	self.pos == self.buf.len()
64	+	}
65	+	fn take(&mut self, n: usize) -> Result<&'a [u8], ObjectError> {
66	+	let end = self.pos.checked_add(n).ok_or_else(short)?;
67	+	let s = self.buf.get(self.pos..end).ok_or_else(short)?;
68	+	self.pos = end;
69	+	Ok(s)
70	+	}
71	+	pub fn u8(&mut self) -> Result<u8, ObjectError> {
72	+	Ok(self.take(1)?[0])
73	+	}
74	+	pub fn u32(&mut self) -> Result<u32, ObjectError> {
75	+	Ok(u32::from_le_bytes(self.fixed::<4>()?))
76	+	}
77	+	pub fn u64(&mut self) -> Result<u64, ObjectError> {
78	+	Ok(u64::from_le_bytes(self.fixed::<8>()?))
79	+	}
80	+	/// A count; checked against what is left, so a corrupt one cannot ask
81	+	/// for more room than the index could hold.
82	+	pub fn count(&mut self) -> Result<usize, ObjectError> {
83	+	let n = self.u32()? as usize;
84	+	if n > self.buf.len() - self.pos {
85	+	return Err(short());
86	+	}
87	+	Ok(n)
88	+	}
89	+	pub fn fixed<const N: usize>(&mut self) -> Result<[u8; N], ObjectError> {
90	+	Ok(self.take(N)?.try_into().expect("N bytes"))
91	+	}
92	+	pub fn bytes(&mut self) -> Result<&'a [u8], ObjectError> {
93	+	let n = self.u32()? as usize;
94	+	self.take(n)
95	+	}
96	+	pub fn text(&mut self) -> Result<String, ObjectError> {
97	+	String::from_utf8(self.bytes()?.to_vec())
98	+	.map_err(\|_\| ObjectError::Schema("index: text is not UTF-8".into()))
99	+	}
100	+	pub fn object(&mut self) -> Result<ObjectRef, ObjectError> {
101	+	Ok(ObjectRef(self.fixed::<32>()?))
102	+	}
103	+	pub fn opt_object(&mut self) -> Result<Option<ObjectRef>, ObjectError> {
104	+	Ok(match self.u8()? {
105	+	0 => None,
106	+	_ => Some(self.object()?),
107	+	})
108	+	}
109	+	}
110	+
111	+	#[cfg(test)]
112	+	mod tests {
113	+	use super::*;
114	+
115	+	#[test]
116	+	fn numbers_and_bytes_round_trip_and_truncation_fails() {
117	+	let mut w = Writer::default();
118	+	w.u8(7);
119	+	w.u32(70_000);
120	+	w.u64(1 << 40);
121	+	w.bytes(b"path/name");
122	+	w.opt_object(&Some(ObjectRef([3; 32])));
123	+	w.opt_object(&None);
124	+	let mut r = Reader::new(&w.0);
125	+	assert_eq!(r.u8().unwrap(), 7);
126	+	assert_eq!(r.u32().unwrap(), 70_000);
127	+	assert_eq!(r.u64().unwrap(), 1 << 40);
128	+	assert_eq!(r.text().unwrap(), "path/name");
129	+	assert_eq!(r.opt_object().unwrap(), Some(ObjectRef([3; 32])));
130	+	assert_eq!(r.opt_object().unwrap(), None);
131	+	assert!(r.at_end());
132	+	let mut r = Reader::new(&w.0[..w.0.len() - 3]);
133	+	r.fixed::<13>().unwrap();
134	+	assert!(r.text().is_ok());
135	+	assert!(r.opt_object().is_err());
136	+	}
137	+	}

		…	1102 unchanged lines
1103	1103		.put(ObjectType::Blob, &Self::blob_for(content).encode())?)
1104	1104		}
1105	1105
	1106	+	/// This workspace's state index (oxygen#41): its working copy's base,
	1107	+	/// saved so a snapshot reads it rather than replaying history.
	1108	+	fn state_index_path(&self) -> PathBuf {
	1109	+	self.oxy
	1110	+	.join("index")
	1111	+	.join(format!("state-{}", self.workspace.to_hex()))
	1112	+	}
	1113	+
	1114	+	/// The history-only state of `deps` (as [`Repo::load_state_history`]),
	1115	+	/// from this workspace's state index when it holds that history: every
	1116	+	/// one of `deps` is in it and their heads are its heads. Otherwise it
	1117	+	/// is loaded from history and indexed for next time.
	1118	+	pub fn load_state_indexed(&self, deps: &[ChangeHash]) -> Result<State> {
	1119	+	if let Some(st) = self.read_state_index(deps) {
	1120	+	#[cfg(test)]
	1121	+	assert_eq!(
	1122	+	st.write_index(),
	1123	+	self.load_state_history(deps)?.write_index(),
	1124	+	"a state index holds the state history gives"
	1125	+	);
	1126	+	return Ok(st);
	1127	+	}
	1128	+	let st = self.load_state_history(deps)?;
	1129	+	self.write_state_index(deps, &st);
	1130	+	Ok(st)
	1131	+	}
	1132	+
	1133	+	fn read_state_index(&self, deps: &[ChangeHash]) -> Option<State> {
	1134	+	let _t = crate::timing::phase("load: state index");
	1135	+	let bytes = fs::read(self.state_index_path()).ok()?;
	1136	+	let mut r = crate::flat::Reader::new(&bytes);
	1137	+	let mut heads = Vec::new();
	1138	+	for _ in 0..r.count().ok()? {
	1139	+	heads.push(r.object().ok()?);
	1140	+	}
	1141	+	let n = 4 + 32 * heads.len();
	1142	+	let st = State::read_index(&bytes[n..]).ok()?;
	1143	+	if !deps.iter().all(\|d\| st.contains(d)) {
	1144	+	return None;
	1145	+	}
	1146	+	let mut have = st.maximal(deps);
	1147	+	have.sort();
	1148	+	(have == heads).then_some(st)
	1149	+	}
	1150	+
	1151	+	/// Save `st`, the history-only state of `deps`, as this workspace's
	1152	+	/// state index; quietly nothing when it cannot be (it is only a cache).
	1153	+	pub(crate) fn write_state_index(&self, deps: &[ChangeHash], st: &State) {
	1154	+	let _t = crate::timing::phase("write: state index");
	1155	+	let Some(body) = st.write_index() else {
	1156	+	return;
	1157	+	};
	1158	+	let mut heads = st.maximal(deps);
	1159	+	heads.sort();
	1160	+	let mut w = crate::flat::Writer::default();
	1161	+	w.count(heads.len());
	1162	+	for h in &heads {
	1163	+	w.object(h);
	1164	+	}
	1165	+	w.fixed(&body);
	1166	+	let path = self.state_index_path();
	1167	+	let tmp = path.with_extension("tmp");
	1168	+	let _ = fs::create_dir_all(self.oxy.join("index"))
	1169	+	.and_then(\|_\| fs::write(&tmp, &w.0))
	1170	+	.and_then(\|_\| fs::rename(&tmp, &path));
	1171	+	}
	1172	+
1106	1173		fn locks_dir(&self) -> PathBuf {
1107	1174		self.oxy.join("locks")
1108	1175		}
		…	650 unchanged lines

		…	305 unchanged lines
306	306		// manifest already knows equal to it.
307	307		let mut base = {
308	308		let _t = crate::timing::phase("snapshot: load base history");
309		-	self.load_state_history(&old_wc.deps)?
	309	+	self.load_state_indexed(&old_wc.deps)?
310	310		};
311	311		let view = {
312	312		let _t = crate::timing::phase("snapshot: tree view");
		…	2208 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

		…	8 unchanged lines
9	9		pub mod diff;
10	10		pub mod durable;
11	11		pub mod fasthash;
	12	+	pub mod flat;
12	13		pub mod graph;
13	14		pub mod hash;
14	15		pub mod identity;
		…	16 unchanged lines

		…	85 unchanged lines
86	86		/// The text blob and line count of each insert in `edits` left without
87	87		/// its lines, in order: read when the graph is built.
88	88		texts: Vec<TextRef>,
	89	+	/// Its graph key, once worked out (or read from an index); reset by
	90	+	/// any edit added.
	91	+	key: std::sync::OnceLock<[u8; 32]>,
89	92		}
90	93
91	94		#[derive(Clone)]
92	95		enum DeferredBase {
93	96		Inline(Value),
94	97		Blob(ObjectRef),
	98	+	}
	99	+
	100	+	/// A local index of a history-only state (oxygen#41), in the flat layout
	101	+	/// of [`crate::flat`]: its change metadata, tree (with its view), replace
	102	+	/// records and every file's deferred history with its graph key, so a
	103	+	/// command reads it rather than replaying history. Derived only: written
	104	+	/// from a state loaded the long way, and read back as the same state.
	105	+	impl State {
	106	+	const INDEX_MAGIC: &'static [u8] = b"oxy state index 1\n";
	107	+
	108	+	/// The index of this state, or `None` when it has anything an index
	109	+	/// does not hold: a built graph, or text in memory (a change added
	110	+	/// whole rather than as its skeleton).
	111	+	pub fn write_index(&self) -> Option<Vec<u8>> {
	112	+	use crate::flat::Writer;
	113	+	let deferred = self.deferred.as_ref()?;
	114	+	if !self.files.is_empty() {
	115	+	return None;
	116	+	}
	117	+	let atom = \|w: &mut Writer, a: &AtomRef\| match a {
	118	+	AtomRef::Start => w.u8(0),
	119	+	AtomRef::End => w.u8(1),
	120	+	AtomRef::Atom { change, index } => {
	121	+	w.u8(2);
	122	+	w.object(change);
	123	+	w.u32(*index);
	124	+	}
	125	+	};
	126	+	let mut w = Writer::default();
	127	+	w.fixed(Self::INDEX_MAGIC);
	128	+	let mut changes: Vec<(&ChangeHash, &Arc<ChangeMeta>)> = self.changes.iter().collect();
	129	+	changes.sort_by_key(\|(h, _)\| **h);
	130	+	w.count(changes.len());
	131	+	for (h, m) in changes {
	132	+	w.object(h);
	133	+	w.fixed(&m.change_id.0);
	134	+	w.count(m.deps.len());
	135	+	for d in &m.deps {
	136	+	w.object(d);
	137	+	}
	138	+	w.object(&m.author);
	139	+	w.u64(m.hlc.wall_ms);
	140	+	w.u32(m.hlc.logical);
	141	+	w.bytes(m.message.as_bytes());
	142	+	w.u8(m.kind.tag() as u8);
	143	+	}
	144	+	// The tree and the files' histories as blocks of their own, so a
	145	+	// reader decodes them side by side.
	146	+	let mut tw = Writer::default();
	147	+	self.tree.write_flat(&mut tw);
	148	+	w.bytes(&tw.0);
	149	+	let mut replaces: Vec<(&NodeId, &Vec<ReplaceRecord>)> = self.replaces.iter().collect();
	150	+	replaces.sort_by_key(\|(n, _)\| **n);
	151	+	w.count(replaces.len());
	152	+	for (n, recs) in replaces {
	153	+	w.fixed(&n.0);
	154	+	w.count(recs.len());
	155	+	// In any order: which record is live does not depend on it.
	156	+	let mut recs: Vec<&ReplaceRecord> = recs.iter().collect();
	157	+	recs.sort();
	158	+	for (c, old, new) in recs {
	159	+	w.object(c);
	160	+	w.opt_object(old);
	161	+	w.opt_object(new);
	162	+	}
	163	+	}
	164	+	let outer = w;
	165	+	let mut w = Writer::default();
	166	+	let mut nodes: Vec<(&NodeId, &Arc<Deferred>)> = deferred.iter().collect();
	167	+	nodes.sort_by_key(\|(n, _)\| **n);
	168	+	w.count(nodes.len());
	169	+	for (n, d) in nodes {
	170	+	w.fixed(&n.0);
	171	+	match &d.base {
	172	+	None => w.u8(0),
	173	+	Some(DeferredBase::Blob(r)) => {
	174	+	w.u8(1);
	175	+	w.object(r);
	176	+	}
	177	+	Some(DeferredBase::Inline(v)) => {
	178	+	w.u8(2);
	179	+	w.bytes(&cbor::encode(v));
	180	+	}
	181	+	}
	182	+	// Each change's edits with the texts of its inserts, sorted by
	183	+	// change: a graph does not depend on the order changes applied
	184	+	// in, and the index is then the same however history was read.
	185	+	let mut texts = d.texts.iter();
	186	+	let mut per_change: Vec<(&ChangeHash, &Vec<Edit>, Vec<&TextRef>)> = Vec::new();
	187	+	for (c, edits) in &d.edits {
	188	+	let n = edits
	189	+	.iter()
	190	+	.filter(\|e\| matches!(e, Edit::Insert { lines, .. } if lines.is_empty()))
	191	+	.count();
	192	+	per_change.push((c, edits, texts.by_ref().take(n).collect()));
	193	+	}
	194	+	per_change.sort_by_key(\|(c, _, _)\| **c);
	195	+	w.count(per_change.len());
	196	+	for (c, edits, _) in &per_change {
	197	+	w.object(c);
	198	+	w.count(edits.len());
	199	+	for e in edits.iter() {
	200	+	match e {
	201	+	Edit::Insert {
	202	+	node,
	203	+	after,
	204	+	before,
	205	+	lines,
	206	+	} => {
	207	+	if !lines.is_empty() {
	208	+	return None;
	209	+	}
	210	+	w.u8(0);
	211	+	w.fixed(&node.0);
	212	+	atom(&mut w, after);
	213	+	atom(&mut w, before);
	214	+	}
	215	+	Edit::Delete { node, atoms } => {
	216	+	w.u8(1);
	217	+	w.fixed(&node.0);
	218	+	w.count(atoms.len());
	219	+	for r in atoms {
	220	+	w.object(&r.change);
	221	+	w.u32(r.from);
	222	+	w.u32(r.to);
	223	+	}
	224	+	}
	225	+	Edit::Replace { .. } => return None,
	226	+	}
	227	+	}
	228	+	}
	229	+	let texts: Vec<&TextRef> = per_change
	230	+	.iter()
	231	+	.flat_map(\|(_, _, t)\| t.iter().copied())
	232	+	.collect();
	233	+	w.count(texts.len());
	234	+	for t in texts {
	235	+	match t {
	236	+	TextRef::Blob(r, count, form) => {
	237	+	w.u8(0);
	238	+	w.object(r);
	239	+	w.u32(*count);
	240	+	w.u8(match form {
	241	+	crate::objects::TextForm::Cbor => 0,
	242	+	crate::objects::TextForm::Raw => 1,
	243	+	crate::objects::TextForm::CborFallback => 2,
	244	+	});
	245	+	}
	246	+	TextRef::Inline { change, start, end } => {
	247	+	w.u8(1);
	248	+	w.object(change);
	249	+	w.u32(*start);
	250	+	w.u32(*end);
	251	+	}
	252	+	}
	253	+	}
	254	+	let mut h = blake3::Hasher::new();
	255	+	h.update(b"oxy graph key 1\0");
	256	+	h.update(&n.0);
	257	+	w.fixed(d.key.get_or_init(\|\| d.graph_key(h)));
	258	+	}
	259	+	let mut outer = outer;
	260	+	outer.bytes(&w.0);
	261	+	Some(outer.0)
	262	+	}
	263	+
	264	+	/// The state an index holds (see [`State::write_index`]).
	265	+	pub fn read_index(bytes: &[u8]) -> Result<State, ObjectError> {
	266	+	use crate::flat::Reader;
	267	+	let bad = \|what: &str\| ObjectError::Schema(format!("state index: {what}"));
	268	+	let mut r = Reader::new(bytes);
	269	+	if r.fixed::<18>()?.as_slice() != Self::INDEX_MAGIC {
	270	+	return Err(bad("not a state index"));
	271	+	}
	272	+	let node = \|r: &mut Reader\| -> Result<NodeId, ObjectError> { Ok(NodeId(r.fixed::<16>()?)) };
	273	+	let mut st = State::new_history_only();
	274	+	let t = crate::timing::phase("index: changes");
	275	+	let n = r.count()?;
	276	+	st.changes.reserve(n);
	277	+	for _ in 0..n {
	278	+	let h = r.object()?;
	279	+	let change_id = crate::ids::ChangeId(r.fixed::<16>()?);
	280	+	let mut deps = Vec::new();
	281	+	for _ in 0..r.count()? {
	282	+	deps.push(r.object()?);
	283	+	}
	284	+	let meta = ChangeMeta {
	285	+	change_id,
	286	+	deps,
	287	+	author: r.object()?,
	288	+	hlc: Hlc {
	289	+	wall_ms: r.u64()?,
	290	+	logical: r.u32()?,
	291	+	},
	292	+	message: r.text()?,
	293	+	kind: ChangeKind::from_tag(r.u8()? as u64)?,
	294	+	};
	295	+	st.changes.insert(h, Arc::new(meta));
	296	+	}
	297	+	drop(t);
	298	+	let tree_bytes = r.bytes()?;
	299	+	for _ in 0..r.count()? {
	300	+	let n = node(&mut r)?;
	301	+	let mut recs = Vec::new();
	302	+	for _ in 0..r.count()? {
	303	+	recs.push((r.object()?, r.opt_object()?, r.opt_object()?));
	304	+	}
	305	+	st.replaces.insert(n, recs);
	306	+	}
	307	+	let deferred_bytes = r.bytes()?;
	308	+	if !r.at_end() {
	309	+	return Err(bad("trailing bytes"));
	310	+	}
	311	+	let (tree, deferred) = rayon::join(
	312	+	\|\| TreeGraph::read_flat(&mut Reader::new(tree_bytes)),
	313	+	\|\| Self::read_deferred(deferred_bytes),
	314	+	);
	315	+	st.tree = tree?;
	316	+	st.deferred = Some(deferred?);
	317	+	Ok(st)
	318	+	}
	319	+
	320	+	fn read_deferred(bytes: &[u8]) -> Result<HashMap<NodeId, Arc<Deferred>>, ObjectError> {
	321	+	use crate::flat::Reader;
	322	+	let _t = crate::timing::phase("index: deferred");
	323	+	let bad = \|what: &str\| ObjectError::Schema(format!("state index: {what}"));
	324	+	let node = \|r: &mut Reader\| -> Result<NodeId, ObjectError> { Ok(NodeId(r.fixed::<16>()?)) };
	325	+	let atom = \|r: &mut Reader\| -> Result<AtomRef, ObjectError> {
	326	+	Ok(match r.u8()? {
	327	+	0 => AtomRef::Start,
	328	+	1 => AtomRef::End,
	329	+	2 => AtomRef::Atom {
	330	+	change: r.object()?,
	331	+	index: r.u32()?,
	332	+	},
	333	+	_ => return Err(bad("atom")),
	334	+	})
	335	+	};
	336	+	let mut r = Reader::new(bytes);
	337	+	let mut deferred: HashMap<NodeId, Arc<Deferred>> = HashMap::new();
	338	+	let n = r.count()?;
	339	+	deferred.reserve(n);
	340	+	for _ in 0..n {
	341	+	let id = node(&mut r)?;
	342	+	let base = match r.u8()? {
	343	+	0 => None,
	344	+	1 => Some(DeferredBase::Blob(r.object()?)),
	345	+	_ => Some(DeferredBase::Inline(cbor::decode(r.bytes()?)?)),
	346	+	};
	347	+	let mut edits = Vec::new();
	348	+	for _ in 0..r.count()? {
	349	+	let c = r.object()?;
	350	+	let mut es = Vec::new();
	351	+	for _ in 0..r.count()? {
	352	+	es.push(match r.u8()? {
	353	+	0 => Edit::Insert {
	354	+	node: node(&mut r)?,
	355	+	after: atom(&mut r)?,
	356	+	before: atom(&mut r)?,
	357	+	lines: crate::lines::Lines::default(),
	358	+	},
	359	+	1 => {
	360	+	let node = node(&mut r)?;
	361	+	let mut atoms = Vec::new();
	362	+	for _ in 0..r.count()? {
	363	+	atoms.push(crate::objects::AtomRange {
	364	+	change: r.object()?,
	365	+	from: r.u32()?,
	366	+	to: r.u32()?,
	367	+	});
	368	+	}
	369	+	Edit::Delete { node, atoms }
	370	+	}
	371	+	_ => return Err(bad("edit")),
	372	+	});
	373	+	}
	374	+	edits.push((c, es));
	375	+	}
	376	+	let mut texts = Vec::new();
	377	+	for _ in 0..r.count()? {
	378	+	texts.push(match r.u8()? {
	379	+	0 => TextRef::Blob(
	380	+	r.object()?,
	381	+	r.u32()?,
	382	+	match r.u8()? {
	383	+	0 => crate::objects::TextForm::Cbor,
	384	+	1 => crate::objects::TextForm::Raw,
	385	+	_ => crate::objects::TextForm::CborFallback,
	386	+	},
	387	+	),
	388	+	_ => TextRef::Inline {
	389	+	change: r.object()?,
	390	+	start: r.u32()?,
	391	+	end: r.u32()?,
	392	+	},
	393	+	});
	394	+	}
	395	+	let d = Deferred {
	396	+	base,
	397	+	edits,
	398	+	texts,
	399	+	key: std::sync::OnceLock::from(r.fixed::<32>()?),
	400	+	};
	401	+	deferred.insert(id, Arc::new(d));
	402	+	}
	403	+	if !r.at_end() {
	404	+	return Err(bad("trailing bytes"));
	405	+	}
	406	+	Ok(deferred)
	407	+	}
95	408		}
96	409
97	410		impl Clone for State {
		…	405 unchanged lines
503	816		h.update(&[0]);
504	817		return Some(*h.finalize().as_bytes());
505	818		};
	819	+	Some(*d.key.get_or_init(\|\| d.graph_key(h)))
	820	+	}
	821	+
	822	+	pub fn len(&self) -> usize {
	823	+	self.changes.len()
	824	+	}
	825	+	}
	826	+
	827	+	impl Deferred {
	828	+	/// See [`State::graph_key`]: `h` has taken the node already.
	829	+	fn graph_key(&self, mut h: blake3::Hasher) -> [u8; 32] {
	830	+	let d = self;
506	831		match &d.base {
507	832		None => h.update(&[0]),
508	833		Some(DeferredBase::Blob(r)) => h.update(&[1]).update(&r.0),
		…	6 unchanged lines
515	840		for c in changes {
516	841		h.update(&c.0);
517	842		}
518		-	Some(*h.finalize().as_bytes())
	843	+	*h.finalize().as_bytes()
519	844		}
	845	+	}
520	846
521		-	pub fn len(&self) -> usize {
522		-	self.changes.len()
523		-	}
	847	+	impl State {
524	848		pub fn is_empty(&self) -> bool {
525	849		self.changes.is_empty()
526	850		}
		…	343 unchanged lines
870	1194		base: Some(base),
871	1195		edits: Vec::new(),
872	1196		texts: Vec::new(),
	1197	+	key: Default::default(),
873	1198		}),
874	1199		);
875	1200		}
		…	104 unchanged lines
980	1305		let d = Arc::make_mut(deferred.entry(node).or_default());
981	1306		d.edits.push((h, edits));
982	1307		d.texts.extend(node_texts);
	1308	+	d.key = Default::default();
983	1309		}
984	1310		}
985	1311		}
		…	1067 unchanged lines

		…	8 unchanged lines
9	9		/// `(change, index into that change's tree_ops)`.
10	10		pub type OpKey = (ChangeHash, u32);
11	11
	12	+	/// The graph's own maps: keyed by hashes and random ids, which need no
	13	+	/// SipHash (see [`crate::fasthash`]).
	14	+	type Map<K, V> = crate::fasthash::FastMap<K, V>;
	15	+
	16	+	/// A node's placement or mode atoms, sorted: nearly always one, held
	17	+	/// without an allocation.
	18	+	#[derive(Clone, Debug, Default, PartialEq, Eq)]
	19	+	enum KeySet {
	20	+	#[default]
	21	+	Empty,
	22	+	One(OpKey),
	23	+	Many(Vec<OpKey>),
	24	+	}
	25	+
	26	+	impl KeySet {
	27	+	fn insert(&mut self, k: OpKey) {
	28	+	match self {
	29	+	KeySet::Empty => *self = KeySet::One(k),
	30	+	KeySet::One(a) if *a == k => {}
	31	+	KeySet::One(a) => {
	32	+	let a = *a;
	33	+	*self = KeySet::Many(if a < k { vec![a, k] } else { vec![k, a] });
	34	+	}
	35	+	KeySet::Many(v) => {
	36	+	if let Err(i) = v.binary_search(&k) {
	37	+	v.insert(i, k);
	38	+	}
	39	+	}
	40	+	}
	41	+	}
	42	+	fn remove(&mut self, k: &OpKey) {
	43	+	match self {
	44	+	KeySet::One(a) if a == k => *self = KeySet::Empty,
	45	+	KeySet::Many(v) => {
	46	+	if let Ok(i) = v.binary_search(k) {
	47	+	v.remove(i);
	48	+	}
	49	+	if v.len() == 1 {
	50	+	*self = KeySet::One(v[0]);
	51	+	} else if v.is_empty() {
	52	+	*self = KeySet::Empty;
	53	+	}
	54	+	}
	55	+	_ => {}
	56	+	}
	57	+	}
	58	+	fn as_slice(&self) -> &[OpKey] {
	59	+	match self {
	60	+	KeySet::Empty => &[],
	61	+	KeySet::One(a) => std::slice::from_ref(a),
	62	+	KeySet::Many(v) => v,
	63	+	}
	64	+	}
	65	+	fn iter(&self) -> std::slice::Iter<'_, OpKey> {
	66	+	self.as_slice().iter()
	67	+	}
	68	+	fn len(&self) -> usize {
	69	+	self.as_slice().len()
	70	+	}
	71	+	fn is_empty(&self) -> bool {
	72	+	matches!(self, KeySet::Empty)
	73	+	}
	74	+	}
	75	+
	76	+	impl<'a> IntoIterator for &'a KeySet {
	77	+	type Item = &'a OpKey;
	78	+	type IntoIter = std::slice::Iter<'a, OpKey>;
	79	+	fn into_iter(self) -> Self::IntoIter {
	80	+	self.iter()
	81	+	}
	82	+	}
	83	+
12	84		#[derive(Clone, Debug, PartialEq, Eq)]
13	85		pub struct Placement {
14	86		pub node: NodeId,
		…	3 unchanged lines
18	90
19	91		#[derive(Clone, Debug, Default)]
20	92		pub struct TreeGraph {
21		-	kinds: HashMap<NodeId, NodeKind>,
22		-	introduced: HashMap<NodeId, ChangeHash>,
23		-	placements: HashMap<OpKey, Placement>,
24		-	modes: HashMap<OpKey, (NodeId, Mode)>,
	93	+	kinds: Map<NodeId, NodeKind>,
	94	+	introduced: Map<NodeId, ChangeHash>,
	95	+	placements: Map<OpKey, Placement>,
	96	+	modes: Map<OpKey, (NodeId, Mode)>,
25	97		/// Placement atoms retired by `RemoveNode`/`Move`, and mode atoms retired
26	98		/// by `SetMode`. Kept apart because `AddNode` introduces one of each
27	99		/// under the same key.
28		-	deleted_placements: HashMap<OpKey, BTreeSet<ChangeHash>>,
29		-	deleted_modes: HashMap<OpKey, BTreeSet<ChangeHash>>,
30		-	placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
31		-	modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
	100	+	deleted_placements: Map<OpKey, BTreeSet<ChangeHash>>,
	101	+	deleted_modes: Map<OpKey, BTreeSet<ChangeHash>>,
	102	+	placements_of: Map<NodeId, KeySet>,
	103	+	modes_of: Map<NodeId, KeySet>,
32	104		/// The live subsets of `placements_of` and `modes_of`, kept as changes
33	105		/// apply, so the view walks what is live rather than all history.
34		-	live_placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
35		-	live_modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
	106	+	live_placements_of: Map<NodeId, KeySet>,
	107	+	live_modes_of: Map<NodeId, KeySet>,
36	108		/// The view, once computed, with the path of each directory in it;
37	109		/// kept up to date as ops apply when that is simple (see
38	110		/// `update_view`), cleared otherwise.
		…	605 unchanged lines
644	716		pub fn to_value(&self) -> crate::cbor::Value {
645	717		use crate::cbor::Value;
646	718		let opkey = \|k: &OpKey\| vec![Value::Bytes(k.0 .0.to_vec()), Value::Uint(k.1 as u64)];
647		-	let deleters = \|m: &HashMap<OpKey, BTreeSet<ChangeHash>>\| {
	719	+	let deleters = \|m: &Map<OpKey, BTreeSet<ChangeHash>>\| {
648	720		let mut ks: Vec<&OpKey> = m.keys().collect();
649	721		ks.sort();
650	722		Value::Array(
		…	107 unchanged lines
758	830		}
759	831		let deleters = \|v: &crate::cbor::Value,
760	832		what: &str\|
761		-	-> Result<HashMap<OpKey, BTreeSet<ChangeHash>>, ObjectError> {
762		-	let mut out = HashMap::new();
	833	+	-> Result<Map<OpKey, BTreeSet<ChangeHash>>, ObjectError> {
	834	+	let mut out = Map::default();
763	835		for d in array(v, what)? {
764	836		let e = array(d, what)?;
765	837		if e.len() != 3 {
		…	29 unchanged lines
795	867		let keys: Vec<OpKey> = g.modes.keys().copied().collect();
796	868		for k in keys {
797	869		g.index_mode(k);
	870	+	}
	871	+	Ok(g)
	872	+	}
	873	+	}
	874	+
	875	+	/// The tree in the flat layout of a local index (oxygen#41), with its view
	876	+	/// when that has no conflicts, so a loaded tree need not work it out again.
	877	+	impl TreeGraph {
	878	+	pub(crate) fn write_flat(&self, w: &mut crate::flat::Writer) {
	879	+	let key = \|w: &mut crate::flat::Writer, k: &OpKey\| {
	880	+	w.object(&k.0);
	881	+	w.u32(k.1);
	882	+	};
	883	+	let mut kinds: Vec<(&NodeId, &NodeKind)> = self.kinds.iter().collect();
	884	+	kinds.sort_by_key(\|(n, _)\| **n);
	885	+	w.count(kinds.len());
	886	+	for (n, k) in kinds {
	887	+	w.fixed(&n.0);
	888	+	w.u8(k.tag() as u8);
	889	+	}
	890	+	let mut intro: Vec<(&NodeId, &ChangeHash)> = self.introduced.iter().collect();
	891	+	intro.sort();
	892	+	w.count(intro.len());
	893	+	for (n, c) in intro {
	894	+	w.fixed(&n.0);
	895	+	w.object(c);
	896	+	}
	897	+	let mut pl: Vec<(&OpKey, &Placement)> = self.placements.iter().collect();
	898	+	pl.sort_by_key(\|(k, _)\| **k);
	899	+	w.count(pl.len());
	900	+	for (k, p) in pl {
	901	+	key(w, k);
	902	+	w.fixed(&p.node.0);
	903	+	w.fixed(&p.parent.0);
	904	+	w.bytes(p.name.as_bytes());
	905	+	}
	906	+	let mut modes: Vec<(&OpKey, &(NodeId, Mode))> = self.modes.iter().collect();
	907	+	modes.sort_by_key(\|(k, _)\| **k);
	908	+	w.count(modes.len());
	909	+	for (k, (n, m)) in modes {
	910	+	key(w, k);
	911	+	w.fixed(&n.0);
	912	+	w.u8(m.bits() as u8);
	913	+	}
	914	+	for m in [&self.deleted_placements, &self.deleted_modes] {
	915	+	let mut ks: Vec<(&OpKey, &BTreeSet<ChangeHash>)> = m.iter().collect();
	916	+	ks.sort_by_key(\|(k, _)\| **k);
	917	+	w.count(ks.len());
	918	+	for (k, by) in ks {
	919	+	key(w, k);
	920	+	w.count(by.len());
	921	+	for c in by {
	922	+	w.object(c);
	923	+	}
	924	+	}
	925	+	}
	926	+	// The view as a block of its own, decoded beside the maps.
	927	+	let outer = std::mem::take(w);
	928	+	let view = self.view();
	929	+	if view.conflicts.is_empty() {
	930	+	w.u8(1);
	931	+	w.count(view.entries.len());
	932	+	for (path, e) in view.entries.iter() {
	933	+	w.bytes(path.as_bytes());
	934	+	w.fixed(&e.node.0);
	935	+	w.u8(e.kind.tag() as u8);
	936	+	w.u8(e.mode.bits() as u8);
	937	+	key(w, &e.placement);
	938	+	match &e.mode_atom {
	939	+	None => w.u8(0),
	940	+	Some(k) => {
	941	+	w.u8(1);
	942	+	key(w, k);
	943	+	}
	944	+	}
	945	+	}
	946	+	} else {
	947	+	w.u8(0);
	948	+	}
	949	+	let view_bytes = std::mem::replace(w, outer);
	950	+	w.bytes(&view_bytes.0);
	951	+	}
	952	+
	953	+	pub(crate) fn read_flat(
	954	+	r: &mut crate::flat::Reader,
	955	+	) -> Result<TreeGraph, crate::objects::ObjectError> {
	956	+	use crate::objects::ObjectError;
	957	+	let node = \|r: &mut crate::flat::Reader\| -> Result<NodeId, ObjectError> {
	958	+	Ok(NodeId(r.fixed::<16>()?))
	959	+	};
	960	+	let key = \|r: &mut crate::flat::Reader\| -> Result<OpKey, ObjectError> {
	961	+	Ok((r.object()?, r.u32()?))
	962	+	};
	963	+	let mut g = TreeGraph::new();
	964	+	let t = crate::timing::phase("index: tree maps");
	965	+	for _ in 0..r.count()? {
	966	+	let n = node(r)?;
	967	+	g.kinds.insert(n, NodeKind::from_tag(r.u8()? as u64)?);
	968	+	}
	969	+	for _ in 0..r.count()? {
	970	+	let n = node(r)?;
	971	+	g.introduced.insert(n, r.object()?);
	972	+	}
	973	+	for _ in 0..r.count()? {
	974	+	let k = key(r)?;
	975	+	let p = Placement {
	976	+	node: node(r)?,
	977	+	parent: node(r)?,
	978	+	name: r.text()?,
	979	+	};
	980	+	g.placements_of.entry(p.node).or_default().insert(k);
	981	+	g.placements.insert(k, p);
	982	+	}
	983	+	for _ in 0..r.count()? {
	984	+	let k = key(r)?;
	985	+	let n = node(r)?;
	986	+	g.modes.insert(k, (n, Mode::from_bits(r.u8()? as u64)?));
	987	+	g.modes_of.entry(n).or_default().insert(k);
798	988		}
	989	+	for i in 0..2 {
	990	+	let mut m: Map<OpKey, BTreeSet<ChangeHash>> = Map::default();
	991	+	for _ in 0..r.count()? {
	992	+	let k = key(r)?;
	993	+	let mut by = BTreeSet::new();
	994	+	for _ in 0..r.count()? {
	995	+	by.insert(r.object()?);
	996	+	}
	997	+	m.insert(k, by);
	998	+	}
	999	+	if i == 0 {
	1000	+	g.deleted_placements = m;
	1001	+	} else {
	1002	+	g.deleted_modes = m;
	1003	+	}
	1004	+	}
	1005	+	drop(t);
	1006	+	let view_bytes = r.bytes()?;
	1007	+	let (view, ()) = rayon::join(
	1008	+	\|\| Self::read_view(view_bytes),
	1009	+	\|\| {
	1010	+	let _t = crate::timing::phase("index: tree live");
	1011	+	let keys: Vec<OpKey> = g.placements.keys().copied().collect();
	1012	+	for k in keys {
	1013	+	g.index_placement(k);
	1014	+	}
	1015	+	let keys: Vec<OpKey> = g.modes.keys().copied().collect();
	1016	+	for k in keys {
	1017	+	g.index_mode(k);
	1018	+	}
	1019	+	},
	1020	+	);
	1021	+	if let Some(view) = view? {
	1022	+	#[cfg(test)]
	1023	+	assert_eq!(view, g.compute_view(), "an index's view is the tree's");
	1024	+	g.view_cache = std::sync::OnceLock::from(CachedView::new(view));
	1025	+	}
799	1026		Ok(g)
	1027	+	}
	1028	+	}
	1029	+
	1030	+	impl TreeGraph {
	1031	+	/// The view block of a tree's flat form, when it holds one.
	1032	+	fn read_view(bytes: &[u8]) -> Result<Option<TreeView>, crate::objects::ObjectError> {
	1033	+	let _t = crate::timing::phase("index: view");
	1034	+	let mut r = crate::flat::Reader::new(bytes);
	1035	+	if r.u8()? != 1 {
	1036	+	return Ok(None);
	1037	+	}
	1038	+	let key = \|r: &mut crate::flat::Reader\| -> Result<OpKey, crate::objects::ObjectError> {
	1039	+	Ok((r.object()?, r.u32()?))
	1040	+	};
	1041	+	let n = r.count()?;
	1042	+	let mut entries = BTreeMap::new();
	1043	+	for _ in 0..n {
	1044	+	let path = r.text()?;
	1045	+	let e = TreeEntry {
	1046	+	path: path.clone(),
	1047	+	node: NodeId(r.fixed::<16>()?),
	1048	+	kind: NodeKind::from_tag(r.u8()? as u64)?,
	1049	+	mode: Mode::from_bits(r.u8()? as u64)?,
	1050	+	placement: key(&mut r)?,
	1051	+	mode_atom: match r.u8()? {
	1052	+	0 => None,
	1053	+	_ => Some(key(&mut r)?),
	1054	+	},
	1055	+	};
	1056	+	entries.insert(path, e);
	1057	+	}
	1058	+	Ok(Some(TreeView {
	1059	+	entries: std::sync::Arc::new(entries),
	1060	+	conflicts: Vec::new(),
	1061	+	}))
800	1062		}
801	1063		}
802	1064
		…	401 unchanged lines

A state index for the working copy's base f9575918477f

Keyboard