The tree's maps are decoded from a state index when first needed 05059d434aca

A state index keeps the tree's maps as a block of their own, decoded
on first use: reading the view (a status) needs only the view, which
the index holds apart. The index carries a hash of its body, checked
when it is read, so a block decoded later can trust its bytes.

refs #41

Author: Andy McCall @andymccall <[email protected]>
When: 1 month ago · 2026-09-30 10:59 UTC
Signature: ✔ signed by Andy McCall
Hash: 05059d434aca0f61dd413c0b58a5656c6b1a1559c3c0f4497961d8d96d938708
Depends on: 2306a4d24779 252e8cb23fbc 75167672ebcd 982864068a59 a87c7b9d563a d0d52107b074 e83354cdac22 f9575918477f ff0af1ee299d
Depended on by: e5f8eb2a2006 c895bc52e4e0 5552e69c7325 79b5a90ffd43 f9466021286a 4cce912a0953 930e5f3f1682
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: 81 atoms, 0 tree operations, 4 files

Browse the tree at this change

show whitespace changes

modified Cargo.lock +1 −0

modified crates/oxy-core/Cargo.toml +1 −1

modified crates/oxy-core/src/repo/mod.rs +13 −2

modified crates/oxy-core/src/tree.rs +175 −98

		…	271 unchanged lines
272	272		"cfg-if",
273	273		"constant_time_eq",
274	274		"cpufeatures",
	275	+	"rayon-core",
275	276		]
276	277
277	278		[[package]]
		…	2282 unchanged lines

		…	5 unchanged lines
6	6		description = "Core data model, change graph, and storage for Oxygen"
7	7
8	8		[dependencies]
9		-	blake3 = "1"
	9	+	blake3 = { version = "1", features = ["rayon"] }
10	10		hex = "0.4"
11	11		rand = "0.8"
12	12		similar = "2"
		…	15 unchanged lines

		…	1137 unchanged lines
1138	1138		for _ in 0..r.count().ok()? {
1139	1139		heads.push(r.object().ok()?);
1140	1140		}
1141		-	let n = 4 + 32 * heads.len();
1142		-	let st = State::read_index(&bytes[n..]).ok()?;
	1141	+	let sum = r.object().ok()?;
	1142	+	let body = &bytes[4 + 32 * heads.len() + 32..];
	1143	+	// Checked whole, so a part decoded later (the tree's maps) can
	1144	+	// trust its bytes.
	1145	+	let mut h = blake3::Hasher::new();
	1146	+	h.update_rayon(body);
	1147	+	if *h.finalize().as_bytes() != sum.0 {
	1148	+	return None;
	1149	+	}
	1150	+	let st = State::read_index(body).ok()?;
1143	1151		if !deps.iter().all(\|d\| st.contains(d)) {
1144	1152		return None;
1145	1153		}
		…	16 unchanged lines
1162	1170		for h in &heads {
1163	1171		w.object(h);
1164	1172		}
	1173	+	let mut sum = blake3::Hasher::new();
	1174	+	sum.update_rayon(&body);
	1175	+	w.fixed(sum.finalize().as_bytes());
1165	1176		w.fixed(&body);
1166	1177		let path = self.state_index_path();
1167	1178		let tmp = path.with_extension("tmp");
		…	658 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

		…	88 unchanged lines
89	89		}
90	90
91	91		#[derive(Clone, Debug, Default)]
92		-	pub struct TreeGraph {
	92	+	struct TreeMaps {
93	93		kinds: Map<NodeId, NodeKind>,
94	94		introduced: Map<NodeId, ChangeHash>,
95	95		placements: Map<OpKey, Placement>,
		…	9 unchanged lines
105	105		/// apply, so the view walks what is live rather than all history.
106	106		live_placements_of: Map<NodeId, KeySet>,
107	107		live_modes_of: Map<NodeId, KeySet>,
	108	+	}
	109	+
	110	+	#[derive(Clone, Debug, Default)]
	111	+	pub struct TreeGraph {
	112	+	/// The graph itself; see [`TreeGraph::m`].
	113	+	maps: std::sync::OnceLock<TreeMaps>,
	114	+	/// A state index's encoding of `maps`, decoded when first needed: a
	115	+	/// command that only reads the view (a status) never needs them.
	116	+	raw: Option<std::sync::Arc<Vec<u8>>>,
108	117		/// The view, once computed, with the path of each directory in it;
109	118		/// kept up to date as ops apply when that is simple (see
110	119		/// `update_view`), cleared otherwise.
		…	76 unchanged lines
187	196		Self::default()
188	197		}
189	198
	199	+	/// The graph's maps, decoded from a state index on first use.
	200	+	fn m(&self) -> &TreeMaps {
	201	+	self.maps.get_or_init(\|\| match &self.raw {
	202	+	Some(raw) => {
	203	+	TreeMaps::decode(raw).expect("a state index is checked against its hash when read")
	204	+	}
	205	+	None => TreeMaps::default(),
	206	+	})
	207	+	}
	208	+
	209	+	fn m_mut(&mut self) -> &mut TreeMaps {
	210	+	self.m();
	211	+	self.maps.get_mut().expect("decoded just now")
	212	+	}
	213	+
190	214		/// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.
191	215		pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
192	216		let cached = self.view_cache.take();
		…	28 unchanged lines
221	245		parent,
222	246		name,
223	247		} => {
224		-	self.kinds.insert(node, kind);
225		-	self.introduced.insert(*node, change);
226		-	self.placements.insert(
	248	+	self.m_mut().kinds.insert(node, kind);
	249	+	self.m_mut().introduced.insert(*node, change);
	250	+	self.m_mut().placements.insert(
227	251		key,
228	252		Placement {
229	253		node: *node,
		…	1 unchanged lines
231	255		name: name.clone(),
232	256		},
233	257		);
234		-	self.placements_of.entry(*node).or_default().insert(key);
	258	+	self.m_mut()
	259	+	.placements_of
	260	+	.entry(*node)
	261	+	.or_default()
	262	+	.insert(key);
235	263		self.index_placement(key);
236	264		if *kind != NodeKind::Dir {
237		-	self.modes.insert(key, (node, mode));
238		-	self.modes_of.entry(*node).or_default().insert(key);
	265	+	self.m_mut().modes.insert(key, (node, mode));
	266	+	self.m_mut().modes_of.entry(*node).or_default().insert(key);
239	267		self.index_mode(key);
240	268		}
241	269		}
242	270		TreeOp::RemoveNode { placement, .. } => {
243		-	self.deleted_placements
	271	+	self.m_mut()
	272	+	.deleted_placements
244	273		.entry(op_key(*placement))
245	274		.or_default()
246	275		.insert(change);
		…	5 unchanged lines
252	281		parent,
253	282		name,
254	283		} => {
255		-	self.deleted_placements
	284	+	self.m_mut()
	285	+	.deleted_placements
256	286		.entry(op_key(*old))
257	287		.or_default()
258	288		.insert(change);
259	289		self.index_placement(op_key(*old));
260		-	self.placements.insert(
	290	+	self.m_mut().placements.insert(
261	291		key,
262	292		Placement {
263	293		node: *node,
		…	1 unchanged lines
265	295		name: name.clone(),
266	296		},
267	297		);
268		-	self.placements_of.entry(*node).or_default().insert(key);
	298	+	self.m_mut()
	299	+	.placements_of
	300	+	.entry(*node)
	301	+	.or_default()
	302	+	.insert(key);
269	303		self.index_placement(key);
270	304		}
271	305		TreeOp::SetMode { node, old, mode } => {
272		-	self.deleted_modes
	306	+	self.m_mut()
	307	+	.deleted_modes
273	308		.entry(op_key(*old))
274	309		.or_default()
275	310		.insert(change);
276	311		self.index_mode(op_key(*old));
277		-	self.modes.insert(key, (node, mode));
278		-	self.modes_of.entry(*node).or_default().insert(key);
	312	+	self.m_mut().modes.insert(key, (node, mode));
	313	+	self.m_mut().modes_of.entry(*node).or_default().insert(key);
279	314		self.index_mode(key);
280	315		}
281	316		}
		…	48 unchanged lines
330	365		return true;
331	366		}
332	367		if self
	368	+	.m()
333	369		.live_placements_of
334	370		.get(&node)
335	371		.is_none_or(\|s\| s.len() != 1)
336	372		{
337	373		return false;
338	374		}
339		-	let Some(p) = self.placements.get(&key) else {
	375	+	let Some(p) = self.m().placements.get(&key) else {
340	376		return false;
341	377		};
342	378		let Some(path) = c.dirs.get(&p.parent).map(\|d\| join(d, &p.name)) else {
		…	28 unchanged lines
371	407
372	408		/// Drop the view entry of `node`'s placement `key`, just retired.
373	409		fn view_remove(&self, c: &mut CachedView, node: NodeId, key: OpKey) -> bool {
374		-	if self.live_placements_of.contains_key(&node) {
	410	+	if self.m().live_placements_of.contains_key(&node) {
375	411		return false;
376	412		}
377		-	let Some(p) = self.placements.get(&key) else {
	413	+	let Some(p) = self.m().placements.get(&key) else {
378	414		return false;
379	415		};
380	416		let Some(path) = c.dirs.get(&p.parent).map(\|d\| join(d, &p.name)) else {
		…	29 unchanged lines
410	446		}
411	447		let mode_atom = lm.iter().map(\|(k, _)\| *k).max();
412	448		let mode = mode_atom
413		-	.and_then(\|k\| self.modes.get(&k).map(\|(_, m)\| *m))
	449	+	.and_then(\|k\| self.m().modes.get(&k).map(\|(_, m)\| *m))
414	450		.unwrap_or_default();
415	451		Some((mode_atom, mode))
416	452		}
417	453
418	454		/// Bring placement `k` in the live index up to date.
419	455		fn index_placement(&mut self, k: OpKey) {
420		-	let Some(node) = self.placements.get(&k).map(\|p\| p.node) else {
	456	+	let Some(node) = self.m_mut().placements.get(&k).map(\|p\| p.node) else {
421	457		return;
422	458		};
423	459		if self.placement_live(&k) {
424		-	self.live_placements_of.entry(node).or_default().insert(k);
425		-	} else if let Some(set) = self.live_placements_of.get_mut(&node) {
	460	+	self.m_mut()
	461	+	.live_placements_of
	462	+	.entry(node)
	463	+	.or_default()
	464	+	.insert(k);
	465	+	} else if let Some(set) = self.m_mut().live_placements_of.get_mut(&node) {
426	466		set.remove(&k);
427	467		if set.is_empty() {
428		-	self.live_placements_of.remove(&node);
	468	+	self.m_mut().live_placements_of.remove(&node);
429	469		}
430	470		}
431	471		}
432	472
433	473		/// Bring mode atom `k` in the live index up to date.
434	474		fn index_mode(&mut self, k: OpKey) {
435		-	let Some(node) = self.modes.get(&k).map(\|(n, _)\| *n) else {
	475	+	let Some(node) = self.m_mut().modes.get(&k).map(\|(n, _)\| *n) else {
436	476		return;
437	477		};
438	478		if self.mode_live(&k) {
439		-	self.live_modes_of.entry(node).or_default().insert(k);
440		-	} else if let Some(set) = self.live_modes_of.get_mut(&node) {
	479	+	self.m_mut()
	480	+	.live_modes_of
	481	+	.entry(node)
	482	+	.or_default()
	483	+	.insert(k);
	484	+	} else if let Some(set) = self.m_mut().live_modes_of.get_mut(&node) {
441	485		set.remove(&k);
442	486		if set.is_empty() {
443		-	self.live_modes_of.remove(&node);
	487	+	self.m_mut().live_modes_of.remove(&node);
444	488		}
445	489		}
446	490		}
		…	3 unchanged lines
450	494		/// back rather than make a second node for one Git path.
451	495		pub fn dead_dirs(&self) -> HashMap<(NodeId, String), (NodeId, OpKey)> {
452	496		let mut out: HashMap<(NodeId, String), (NodeId, OpKey)> = HashMap::new();
453		-	for (k, p) in &self.placements {
	497	+	for (k, p) in &self.m().placements {
454	498		if self.kind(&p.node) != Some(NodeKind::Dir)
455	499		\|\| self.placement_live(k)
456	500		\|\| !self.live_placements(&p.node).is_empty()
		…	14 unchanged lines
471	515		/// Every placement `node` ever had, live or not, with the changes that
472	516		/// retired it (none while live).
473	517		pub fn placement_history(&self, node: &NodeId) -> Vec<(OpKey, &Placement, Vec<ChangeHash>)> {
474		-	self.placements_of
	518	+	self.m()
	519	+	.placements_of
475	520		.get(node)
476	521		.into_iter()
477	522		.flatten()
478	523		.filter_map(\|k\| {
479		-	let p = self.placements.get(k)?;
	524	+	let p = self.m().placements.get(k)?;
480	525		let by = self
	526	+	.m()
481	527		.deleted_placements
482	528		.get(k)
483	529		.map(\|d\| d.iter().copied().collect())
		…	4 unchanged lines
488	534		}
489	535
490	536		fn placement_live(&self, k: &OpKey) -> bool {
491		-	self.deleted_placements.get(k).is_none_or(\|d\| d.is_empty())
	537	+	self.m()
	538	+	.deleted_placements
	539	+	.get(k)
	540	+	.is_none_or(\|d\| d.is_empty())
492	541		}
493	542		fn mode_live(&self, k: &OpKey) -> bool {
494		-	self.deleted_modes.get(k).is_none_or(\|d\| d.is_empty())
	543	+	self.m().deleted_modes.get(k).is_none_or(\|d\| d.is_empty())
495	544		}
496	545
497	546		pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {
498	547		if node.is_root() {
499	548		Some(NodeKind::Dir)
500	549		} else {
501		-	self.kinds.get(node).copied()
	550	+	self.m().kinds.get(node).copied()
502	551		}
503	552		}
504	553
505	554		/// The change whose `AddNode` introduced `node`.
506	555		pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {
507		-	self.introduced.get(node).copied()
	556	+	self.m().introduced.get(node).copied()
508	557		}
509	558
510	559		pub fn placement(&self, k: &OpKey) -> Option<&Placement> {
511		-	self.placements.get(k)
	560	+	self.m().placements.get(k)
512	561		}
513	562
514	563		pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {
515		-	self.live_placements_of
	564	+	self.m()
	565	+	.live_placements_of
516	566		.get(node)
517	567		.into_iter()
518	568		.flat_map(\|ks\| ks.iter())
519		-	.filter_map(\|k\| self.placements.get(k).map(\|p\| (*k, p)))
	569	+	.filter_map(\|k\| self.m().placements.get(k).map(\|p\| (*k, p)))
520	570		.collect()
521	571		}
522	572
523	573		pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {
524		-	self.live_modes_of
	574	+	self.m()
	575	+	.live_modes_of
525	576		.get(node)
526	577		.into_iter()
527	578		.flat_map(\|ks\| ks.iter())
528		-	.filter_map(\|k\| self.modes.get(k).map(\|(_, m)\| (k, m)))
	579	+	.filter_map(\|k\| self.m().modes.get(k).map(\|(_, m)\| (k, m)))
529	580		.collect()
530	581		}
531	582
532	583		/// Every node that has at least one live placement.
533	584		pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
534		-	self.live_placements_of.keys().copied()
	585	+	self.m().live_placements_of.keys().copied()
535	586		}
536	587
537	588		/// Resolve the tree: assign paths, find conflicts.
		…	12 unchanged lines
550	601
551	602		// Live placements grouped by parent.
552	603		let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();
553		-	for ks in self.live_placements_of.values() {
	604	+	for ks in self.m().live_placements_of.values() {
554	605		for k in ks {
555		-	if let Some(p) = self.placements.get(k) {
	606	+	if let Some(p) = self.m().placements.get(k) {
556	607		children.entry(p.parent).or_default().push((*k, p));
557	608		}
558	609		}
		…	4 unchanged lines
563	614
564	615		// Multi-placement and mode conflicts.
565	616		// Only placed nodes: one with no live placement is not in the tree.
566		-	let mut nodes: Vec<NodeId> = self.live_placements_of.keys().copied().collect();
	617	+	let mut nodes: Vec<NodeId> = self.m().live_placements_of.keys().copied().collect();
567	618		nodes.sort();
568	619		let mut multi: HashSet<NodeId> = HashSet::new();
569	620		// Each node's mode and the atom it comes from, for the entries.
		…	26 unchanged lines
596	647		}
597	648		let mode_atom = lm.iter().map(\|(k, _)\| *k).max();
598	649		let mode = mode_atom
599		-	.and_then(\|k\| self.modes.get(&k).map(\|(_, m)\| *m))
	650	+	.and_then(\|k\| self.m().modes.get(&k).map(\|(_, m)\| *m))
600	651		.unwrap_or_default();
601	652		modes.insert(*n, (mode_atom, mode));
602	653		}
		…	128 unchanged lines
731	782		.collect(),
732	783		)
733	784		};
734		-	let mut nodes: Vec<&NodeId> = self.kinds.keys().collect();
	785	+	let mut nodes: Vec<&NodeId> = self.m().kinds.keys().collect();
735	786		nodes.sort();
736		-	let mut pks: Vec<&OpKey> = self.placements.keys().collect();
	787	+	let mut pks: Vec<&OpKey> = self.m().placements.keys().collect();
737	788		pks.sort();
738		-	let mut mks: Vec<&OpKey> = self.modes.keys().collect();
	789	+	let mut mks: Vec<&OpKey> = self.m().modes.keys().collect();
739	790		mks.sort();
740	791		Value::map([
741	792		(
		…	4 unchanged lines
746	797		.map(\|n\| {
747	798		Value::Array(vec![
748	799		Value::Bytes(n.0.to_vec()),
749		-	Value::Uint(self.kinds[n].tag()),
750		-	self.introduced
	800	+	Value::Uint(self.m().kinds[n].tag()),
	801	+	self.m()
	802	+	.introduced
751	803		.get(n)
752	804		.map(\|h\| Value::Bytes(h.0.to_vec()))
753	805		.unwrap_or(Value::Null),
		…	7 unchanged lines
761	813		Value::Array(
762	814		pks.into_iter()
763	815		.map(\|k\| {
764		-	let p = &self.placements[k];
	816	+	let p = &self.m().placements[k];
765	817		let mut v = opkey(k);
766	818		v.extend([
767	819		Value::Bytes(p.node.0.to_vec()),
		…	5 unchanged lines
773	825		.collect(),
774	826		),
775	827		),
776		-	(2, deleters(&self.deleted_placements)),
	828	+	(2, deleters(&self.m().deleted_placements)),
777	829		(
778	830		3,
779	831		Value::Array(
780	832		mks.into_iter()
781	833		.map(\|k\| {
782		-	let (n, m) = &self.modes[k];
	834	+	let (n, m) = &self.m().modes[k];
783	835		let mut v = opkey(k);
784	836		v.extend([Value::Bytes(n.0.to_vec()), Value::Uint(m.bits())]);
785	837		Value::Array(v)
		…	1 unchanged lines
787	839		.collect(),
788	840		),
789	841		),
790		-	(4, deleters(&self.deleted_modes)),
	842	+	(4, deleters(&self.m().deleted_modes)),
791	843		])
792	844		}
793	845
		…	14 unchanged lines
808	860		return Err(ObjectError::Schema("node entry: expected 3 fields".into()));
809	861		}
810	862		let id = node(&e[0])?;
811		-	g.kinds
	863	+	g.m_mut()
	864	+	.kinds
812	865		.insert(id, NodeKind::from_tag(uint(&e[1], "kind")?)?);
813	866		if !e[2].is_null() {
814		-	g.introduced.insert(id, oref(&e[2], "introducer")?);
	867	+	g.m_mut().introduced.insert(id, oref(&e[2], "introducer")?);
815	868		}
816	869		}
817	870		for p in array(field(m, 1, "placements")?, "placements")? {
		…	7 unchanged lines
825	878		parent: node(&e[3])?,
826	879		name: text(&e[4], "name")?.to_owned(),
827	880		};
828		-	g.placements_of.entry(pl.node).or_default().insert(k);
829		-	g.placements.insert(k, pl);
	881	+	g.m_mut()
	882	+	.placements_of
	883	+	.entry(pl.node)
	884	+	.or_default()
	885	+	.insert(k);
	886	+	g.m_mut().placements.insert(k, pl);
830	887		}
831	888		let deleters = \|v: &crate::cbor::Value,
832	889		what: &str\|
		…	14 unchanged lines
847	904		}
848	905		Ok(out)
849	906		};
850		-	g.deleted_placements = deleters(field(m, 2, "deleted placements")?, "deleted placement")?;
	907	+	g.m_mut().deleted_placements =
	908	+	deleters(field(m, 2, "deleted placements")?, "deleted placement")?;
851	909		for md in array(field(m, 3, "modes")?, "modes")? {
852	910		let e = array(md, "mode")?;
853	911		if e.len() != 4 {
		…	1 unchanged lines
855	913		}
856	914		let k = opkey(e)?;
857	915		let n = node(&e[2])?;
858		-	g.modes
	916	+	g.m_mut()
	917	+	.modes
859	918		.insert(k, (n, Mode::from_bits(uint(&e[3], "mode bits")?)?));
860		-	g.modes_of.entry(n).or_default().insert(k);
	919	+	g.m_mut().modes_of.entry(n).or_default().insert(k);
861	920		}
862		-	g.deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;
863		-	let keys: Vec<OpKey> = g.placements.keys().copied().collect();
	921	+	g.m_mut().deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;
	922	+	let keys: Vec<OpKey> = g.m_mut().placements.keys().copied().collect();
864	923		for k in keys {
865	924		g.index_placement(k);
866	925		}
867		-	let keys: Vec<OpKey> = g.modes.keys().copied().collect();
	926	+	let keys: Vec<OpKey> = g.m_mut().modes.keys().copied().collect();
868	927		for k in keys {
869	928		g.index_mode(k);
870	929		}
		…	9 unchanged lines
880	939		w.object(&k.0);
881	940		w.u32(k.1);
882	941		};
883		-	let mut kinds: Vec<(&NodeId, &NodeKind)> = self.kinds.iter().collect();
	942	+	// The maps as a block of their own: a reader keeps it undecoded
	943	+	// until something needs them.
	944	+	let outer = std::mem::take(w);
	945	+	let mut kinds: Vec<(&NodeId, &NodeKind)> = self.m().kinds.iter().collect();
884	946		kinds.sort_by_key(\|(n, _)\| **n);
885	947		w.count(kinds.len());
886	948		for (n, k) in kinds {
887	949		w.fixed(&n.0);
888	950		w.u8(k.tag() as u8);
889	951		}
890		-	let mut intro: Vec<(&NodeId, &ChangeHash)> = self.introduced.iter().collect();
	952	+	let mut intro: Vec<(&NodeId, &ChangeHash)> = self.m().introduced.iter().collect();
891	953		intro.sort();
892	954		w.count(intro.len());
893	955		for (n, c) in intro {
894	956		w.fixed(&n.0);
895	957		w.object(c);
896	958		}
897		-	let mut pl: Vec<(&OpKey, &Placement)> = self.placements.iter().collect();
	959	+	let mut pl: Vec<(&OpKey, &Placement)> = self.m().placements.iter().collect();
898	960		pl.sort_by_key(\|(k, _)\| **k);
899	961		w.count(pl.len());
900	962		for (k, p) in pl {
		…	2 unchanged lines
903	965		w.fixed(&p.parent.0);
904	966		w.bytes(p.name.as_bytes());
905	967		}
906		-	let mut modes: Vec<(&OpKey, &(NodeId, Mode))> = self.modes.iter().collect();
	968	+	let mut modes: Vec<(&OpKey, &(NodeId, Mode))> = self.m().modes.iter().collect();
907	969		modes.sort_by_key(\|(k, _)\| **k);
908	970		w.count(modes.len());
909	971		for (k, (n, m)) in modes {
		…	1 unchanged lines
911	973		w.fixed(&n.0);
912	974		w.u8(m.bits() as u8);
913	975		}
914		-	for m in [&self.deleted_placements, &self.deleted_modes] {
	976	+	for m in [&self.m().deleted_placements, &self.m().deleted_modes] {
915	977		let mut ks: Vec<(&OpKey, &BTreeSet<ChangeHash>)> = m.iter().collect();
916	978		ks.sort_by_key(\|(k, _)\| **k);
917	979		w.count(ks.len());
		…	5 unchanged lines
923	985		}
924	986		}
925	987		}
926		-	// The view as a block of its own, decoded beside the maps.
	988	+	let maps = std::mem::replace(w, outer);
	989	+	w.bytes(&maps.0);
	990	+	// The view as a block of its own.
927	991		let outer = std::mem::take(w);
928	992		let view = self.view();
929	993		if view.conflicts.is_empty() {
		…	23 unchanged lines
953	1017		pub(crate) fn read_flat(
954	1018		r: &mut crate::flat::Reader,
955	1019		) -> Result<TreeGraph, crate::objects::ObjectError> {
	1020	+	let maps = r.bytes()?;
	1021	+	let view = Self::read_view(r.bytes()?)?;
	1022	+	let mut g = TreeGraph {
	1023	+	raw: Some(std::sync::Arc::new(maps.to_vec())),
	1024	+	..TreeGraph::default()
	1025	+	};
	1026	+	if let Some(view) = view {
	1027	+	#[cfg(test)]
	1028	+	assert_eq!(view, g.compute_view(), "an index's view is the tree's");
	1029	+	g.view_cache = std::sync::OnceLock::from(CachedView::new(view));
	1030	+	}
	1031	+	Ok(g)
	1032	+	}
	1033	+	}
	1034	+
	1035	+	impl TreeMaps {
	1036	+	/// The maps block of a tree's flat form.
	1037	+	fn decode(bytes: &[u8]) -> Result<TreeMaps, crate::objects::ObjectError> {
956	1038		use crate::objects::ObjectError;
	1039	+	let _t = crate::timing::phase("index: tree maps");
957	1040		let node = \|r: &mut crate::flat::Reader\| -> Result<NodeId, ObjectError> {
958	1041		Ok(NodeId(r.fixed::<16>()?))
959	1042		};
960	1043		let key = \|r: &mut crate::flat::Reader\| -> Result<OpKey, ObjectError> {
961	1044		Ok((r.object()?, r.u32()?))
962	1045		};
	1046	+	let r = &mut crate::flat::Reader::new(bytes);
963	1047		let mut g = TreeGraph::new();
964		-	let t = crate::timing::phase("index: tree maps");
965	1048		for _ in 0..r.count()? {
966	1049		let n = node(r)?;
967		-	g.kinds.insert(n, NodeKind::from_tag(r.u8()? as u64)?);
	1050	+	g.m_mut()
	1051	+	.kinds
	1052	+	.insert(n, NodeKind::from_tag(r.u8()? as u64)?);
968	1053		}
969	1054		for _ in 0..r.count()? {
970	1055		let n = node(r)?;
971		-	g.introduced.insert(n, r.object()?);
	1056	+	g.m_mut().introduced.insert(n, r.object()?);
972	1057		}
973	1058		for _ in 0..r.count()? {
974	1059		let k = key(r)?;
		…	2 unchanged lines
977	1062		parent: node(r)?,
978	1063		name: r.text()?,
979	1064		};
980		-	g.placements_of.entry(p.node).or_default().insert(k);
981		-	g.placements.insert(k, p);
	1065	+	g.m_mut().placements_of.entry(p.node).or_default().insert(k);
	1066	+	g.m_mut().placements.insert(k, p);
982	1067		}
983	1068		for _ in 0..r.count()? {
984	1069		let k = key(r)?;
985	1070		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);
	1071	+	g.m_mut()
	1072	+	.modes
	1073	+	.insert(k, (n, Mode::from_bits(r.u8()? as u64)?));
	1074	+	g.m_mut().modes_of.entry(n).or_default().insert(k);
988	1075		}
989	1076		for i in 0..2 {
990	1077		let mut m: Map<OpKey, BTreeSet<ChangeHash>> = Map::default();
		…	6 unchanged lines
997	1084		m.insert(k, by);
998	1085		}
999	1086		if i == 0 {
1000		-	g.deleted_placements = m;
	1087	+	g.m_mut().deleted_placements = m;
1001	1088		} else {
1002		-	g.deleted_modes = m;
	1089	+	g.m_mut().deleted_modes = m;
1003	1090		}
1004	1091		}
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));
	1092	+	if !r.at_end() {
	1093	+	return Err(ObjectError::Schema("state index: tree maps".into()));
	1094	+	}
	1095	+	let keys: Vec<OpKey> = g.m().placements.keys().copied().collect();
	1096	+	for k in keys {
	1097	+	g.index_placement(k);
	1098	+	}
	1099	+	let keys: Vec<OpKey> = g.m().modes.keys().copied().collect();
	1100	+	for k in keys {
	1101	+	g.index_mode(k);
1025	1102		}
1026		-	Ok(g)
	1103	+	Ok(g.maps.into_inner().unwrap_or_default())
1027	1104		}
1028	1105		}
1029	1106
		…	436 unchanged lines

The tree's maps are decoded from a state index when first needed 05059d434aca

Keyboard