clover's git

snowbound

1	use crate::{
2	Chunk, Error, ExGuid, FileType, Node, ObjectData, PropertySets, Reference, RevisionIndex,
3	Store, Value,
4	bytes::Cursor,
5	store::{Fragment, ListTail, StoreState, crc, transaction_crc},
6	};
7
8	use std::{
9	collections::{BTreeMap, BTreeSet},
10	sync::Arc,
11	};
12
13	#[cfg(test)]
14	mod tests;
15
16	type Result<T> = std::result::Result<T, Error>;
17
18	#[cfg(test)]
19	thread_local! {
20	/// When set, `fresh_guid` counts from it instead of drawing randomness, so tests can
21	/// compare builds byte for byte.
22	pub(crate) static GUIDS: std::cell::Cell<Option<u64>> = const { std::cell::Cell::new(None) };
23	}
24
25	pub(crate) fn fresh_guid() -> Result<[u8; 16]> {
26	let mut guid = [0; 16];
27	getrandom::fill(&mut guid).map_err(|_| Error {
28	offset: 0,
29	message: "System random source failed",
30	})?;
31	#[cfg(test)]
32	if let Some(next) = GUIDS.get() {
33	GUIDS.set(Some(next + 1));
34	guid[..8].copy_from_slice(&next.to_le_bytes());
35	guid[8..].copy_from_slice(&0x5eed_u64.to_le_bytes());
36	}
37	guid[7] = (guid[7] & 0x0f) | 0x40;
38	guid[8] = (guid[8] & 0x3f) | 0x80;
39	Ok(guid)
40	}
41
42	impl ExGuid {
43	pub(crate) fn encode(self, data: &mut Vec<u8>) {
44	data.extend_from_slice(&self.guid);
45	data.extend_from_slice(&self.n.to_le_bytes());
46	}
47	}
48
49	pub(crate) fn node(id: u16, reference: Option<Reference>, payload: &[u8]) -> Result<Vec<u8>> {
50	let size = 4 + if reference.is_some() { 12 } else { 0 } + payload.len();
51	if size > 0x1fff {
52	return Err(Error {
53	offset: 0,
54	message: "File node exceeds the format size limit",
55	});
56	}
57	let (base, chunk) = match reference {
58	Some(Reference::Data(chunk)) => (1, Some(chunk)),
59	Some(Reference::NodeList(chunk)) => (2, Some(chunk)),
60	None => (0, None),
61	};
62	let header = 0x80000000 | (base << 27) | (u32::try_from(size).unwrap() << 10) | u32::from(id);
63	let mut bytes = header.to_le_bytes().to_vec();
64	if let Some(chunk) = chunk {
65	bytes.extend_from_slice(&chunk.offset.to_le_bytes());
66	bytes.extend_from_slice(
67	&u32::try_from(chunk.length)
68	.map_err(|_| Error {
69	offset: 0,
70	message: "Chunk exceeds the encoded length limit",
71	})?
72	.to_le_bytes(),
73	);
74	}
75	bytes.extend_from_slice(payload);
76	Ok(bytes)
77	}
78
79	/// A `RevisionRoleAndContextDeclarationFND` payload: `rid` current under `context` in the
80	/// default role.
81	pub(crate) fn label_payload(rid: ExGuid, context: ExGuid) -> Vec<u8> {
82	let mut payload = Vec::new();
83	rid.encode(&mut payload);
84	payload.extend_from_slice(&1_u32.to_le_bytes());
85	context.encode(&mut payload);
86	payload
87	}
88
89	pub(crate) fn append(data: &mut Vec<u8>, bytes: &[u8]) -> Result<Chunk> {
90	let length = u64::from(u32::try_from(bytes.len()).map_err(|_| Error {
91	offset: 0,
92	message: "Chunk exceeds the encoded length limit",
93	})?);
94	data.resize(data.len().next_multiple_of(8), 0);
95	let offset = u64::try_from(data.len()).unwrap();
96	data.extend_from_slice(bytes);
97	Ok(Chunk { offset, length })
98	}
99
100	pub(crate) fn append_list(data: &mut Vec<u8>, id: u32, nodes: &[Vec<u8>]) -> Result<Chunk> {
101	append(data, &fragment(id, 0, nodes))
102	}
103
104	/// The file-node list fragment `sequence` of list `id`, holding `nodes` and no successor.
105	fn fragment(id: u32, sequence: u32, nodes: &[Vec<u8>]) -> Vec<u8> {
106	let mut bytes = 0xa4567ab1f5f7f4c4_u64.to_le_bytes().to_vec();
107	bytes.extend_from_slice(&id.to_le_bytes());
108	bytes.extend_from_slice(&sequence.to_le_bytes());
109	for node in nodes {
110	bytes.extend_from_slice(node);
111	}
112	bytes.resize((bytes.len() + 20).next_multiple_of(8) - 20, 0);
113	bytes.extend_from_slice(&u64::MAX.to_le_bytes());
114	bytes.extend_from_slice(&0_u32.to_le_bytes());
115	bytes.extend_from_slice(&0x8bc215c38233ba4b_u64.to_le_bytes());
116	bytes
117	}
118
119	pub(crate) fn compact(id: ExGuid, table: &BTreeMap<u32, [u8; 16]>) -> Result<[u8; 4]> {
120	let index = table
121	.iter()
122	.find_map(|(index, guid)| (*guid == id.guid).then_some(*index))
123	.ok_or(Error {
124	offset: 0,
125	message: "Object identity is absent from its global ID table",
126	})?;
127	if id.n > 255 {
128	return Err(Error {
129	offset: 0,
130	message: "Object extension exceeds CompactID capacity",
131	});
132	}
133	Ok(((index << 8) | id.n).to_le_bytes())
134	}
135
136	/// The global id table entries a property object's references name.
137	pub(crate) fn table_entries(bytes: &[u8]) -> Result<Vec<u32>> {
138	let mut entries = Vec::new();
139	for property in PropertySets::parse(bytes)?.sets.iter().flatten() {
140	if let Value::References { compact_ids, .. } = property.value {
141	entries.extend(
142	compact_ids
143	.chunks_exact(4)
144	.map(|id| u32::from_le_bytes(id.try_into().unwrap()) >> 8),
145	);
146	}
147	}
148	Ok(entries)
149	}
150
151	fn field_length(property: &crate::Property<'_>, set_lengths: &[usize]) -> usize {
152	match &property.value {
153	Value::NoData => 0,
154	Value::Bytes(bytes) => bytes.len() + usize::from(property.id >> 26 & 31 == 7) * 4,
155	Value::References { .. } => usize::from(property.id >> 26 & 1 != 0) * 4,
156	Value::Sets(children) => {
157	let prefix = if property.id >> 26 & 31 == 16 {
158	if children.is_empty() { 4 } else { 8 }
159	} else {
160	0
161	};
162	prefix + children.clone().map(|i| set_lengths[i]).sum::<usize>()
163	}
164	}
165	}
166
167	fn property_set_lengths(properties: &PropertySets<'_>) -> Vec<usize> {
168	let mut lengths = vec![0; properties.sets.len()];
169	for (i, set) in properties.sets.iter().enumerate().rev() {
170	lengths[i] =
171	2 + set.len() * 4 + set.iter().map(|p| field_length(p, &lengths)).sum::<usize>();
172	}
173	lengths
174	}
175
176	fn patch_properties(
177	blob: &[u8],
178	updates: &[(u32, &[u8])],
179	inserts: &[(u32, &[u8])],
180	nested_references: &[u8],
181	) -> Result<Vec<u8>> {
182	let properties = PropertySets::parse(blob)?;
183	let root = &properties.sets[0];
184	let ids = properties.root_ids.as_ptr().addr() - blob.as_ptr().addr();
185	let ids_end = ids + properties.root_ids.len();
186	let body_end = blob.len() - properties.padding.len();
187	let set_lengths = property_set_lengths(&properties);
188	let mut offsets = Vec::with_capacity(root.len());
189	let mut offset = ids_end;
190	for property in root {
191	offsets.push(offset);
192	offset += field_length(property, &set_lengths);
193	}
194	let mut patches = Vec::new();
195	let mut added_ids = Vec::new();
196	let mut added_fields = Vec::new();
197	let mut added_references = Vec::new();
198	let object_header = u32::from_le_bytes(blob[..4].try_into().unwrap());
199	let mut object_count = i64::from(object_header & 0xffffff);
200	let mut seen = BTreeSet::new();
201	for (i, &(property, value)) in updates.iter().chain(inserts).enumerate() {
202	if !seen.insert(property & 0x7fffffff) {
203	return Err(Error {
204	offset: 0,
205	message: "Duplicate property update",
206	});
207	}
208	let kind = (property >> 26) & 31;
209	let valid = match kind {
210	2 => value.is_empty(),
211	3..=6 => value.len() == 1 << (kind - 3),
212	7 => value.len() < 0x40000000,
213	8 => value.len() == 4,
214	9 => value.len().is_multiple_of(4) && value.len() / 4 <= 0xffffff,
215	// An encoded property-set array is inserted whole; its references follow.
216	16 => i >= updates.len() && value.len() >= 4,
217	_ => {
218	return Err(Error {
219	offset: 0,
220	message: "Property type cannot be patched",
221	});
222	}
223	};
224	if !valid || (kind != 2 && property & 0x80000000 != 0) {
225	return Err(Error {
226	offset: 0,
227	message: "Replacement has an invalid property value",
228	});
229	}
230	let matches: Vec<_> = root
231	.iter()
232	.enumerate()
233	.filter(|(_, p)| p.id & 0x7fffffff == property & 0x7fffffff)
234	.collect();
235	let adding = i >= updates.len();
236	if matches.len() != usize::from(!adding) {
237	return Err(Error {
238	offset: 0,
239	message: "Property is missing or duplicated",
240	});
241	}
242	let mut encoded = Vec::new();
243	match kind {
244	7 => encoded.extend_from_slice(&(value.len() as u32).to_le_bytes()),
245	9 => encoded.extend_from_slice(&(value.len() as u32 / 4).to_le_bytes()),
246	_ => {}
247	}
248	if (3..=7).contains(&kind) || kind == 16 {
249	encoded.extend_from_slice(value);
250	}
251	if adding {
252	added_ids.extend_from_slice(&property.to_le_bytes());
253	added_fields.extend_from_slice(&encoded);
254	if (8..=9).contains(&kind) {
255	object_count += (value.len() / 4) as i64;
256	added_references.extend_from_slice(value);
257	}
258	} else {
259	let (index, previous) = matches[0];
260	if kind == 2 && previous.id != property {
261	patches.push((
262	ids + index * 4,
263	ids + index * 4 + 4,
264	index,
265	property.to_le_bytes().to_vec(),
266	));
267	}
268	let start = offsets[index];
269	let end = start + field_length(previous, &set_lengths);
270	if blob[start..end] != encoded {
271	patches.push((start, end, index, encoded));
272	}
273	if let Value::References { compact_ids, .. } = previous.value {
274	object_count += (value.len() / 4) as i64 - (compact_ids.len() / 4) as i64;
275	if compact_ids != value {
276	let start = compact_ids.as_ptr().addr() - blob.as_ptr().addr();
277	patches.push((start, start + compact_ids.len(), index, value.to_vec()));
278	}
279	}
280	}
281	}
282	object_count += (nested_references.len() / 4) as i64;
283	if !(0..=0xffffff).contains(&object_count) {
284	return Err(Error {
285	offset: 0,
286	message: "Object reference stream exceeds the format limit",
287	});
288	}
289	let header = (object_header & 0xff000000) | object_count as u32;
290	if header != object_header {
291	patches.push((0, 4, 0, header.to_le_bytes().to_vec()));
292	}
293	added_references.extend_from_slice(nested_references);
294	if !added_references.is_empty() {
295	let end = 4 + (object_header as usize & 0xffffff) * 4;
296	patches.push((end, end, usize::MAX, added_references));
297	}
298	if !inserts.is_empty() {
299	let count = u16::try_from(root.len() + inserts.len()).map_err(|_| Error {
300	offset: ids - 2,
301	message: "Root property count exceeds the format limit",
302	})?;
303	patches.push((ids - 2, ids, 0, count.to_le_bytes().to_vec()));
304	patches.push((ids_end, ids_end, usize::MAX - 1, added_ids));
305	patches.push((body_end, body_end, usize::MAX, added_fields));
306	}
307	if patches.is_empty() {
308	return Ok(blob.to_vec());
309	}
310	patches.sort_by_key(|(start, end, order, _)| (*start, *end, *order));
311	let mut changed = Vec::new();
312	let mut cursor = 0;
313	for (start, end, _, value) in patches {
314	if start < cursor {
315	return Err(Error {
316	offset: start,
317	message: "Property patches overlap",
318	});
319	}
320	changed.extend_from_slice(&blob[cursor..start]);
321	changed.extend_from_slice(&value);
322	cursor = end;
323	}
324	changed.extend_from_slice(&blob[cursor..body_end]);
325	changed.resize(changed.len().next_multiple_of(8), 0);
326	PropertySets::parse(&changed)?;
327	Ok(changed)
328	}
329
330	pub(crate) struct ObjectEdit<'a> {
331	pub object: ExGuid,
332	pub updates: &'a [(u32, &'a [u8])],
333	pub inserts: &'a [(u32, &'a [u8])],
334	}
335
336	/// Objects of `revision` with `edits` applied.
337	pub(crate) fn patched(
338	revision: &crate::ResolvedRevision<'_>,
339	edits: &[ObjectEdit<'_>],
340	) -> Result<BTreeMap<ExGuid, PropertyObject>> {
341	let mut changed = BTreeMap::new();
342	for edit in edits {
343	if changed.contains_key(&edit.object) {
344	return Err(Error {
345	offset: 0,
346	message: "Duplicate object edit",
347	});
348	}
349	let object = revision.objects.get(&edit.object).ok_or(Error {
350	offset: 0,
351	message: "Object is absent from the active revision",
352	})?;
353	let ObjectData::Properties(blob) = object.data else {
354	return Err(Error {
355	offset: 0,
356	message: "Object does not contain editable properties",
357	});
358	};
359	changed.insert(
360	edit.object,
361	PropertyObject {
362	jcid: object.jcid,
363	bytes: patch_properties(blob, edit.updates, edit.inserts, &[])?,
364	global_ids: Arc::clone(&object.global_ids),
365	},
366	);
367	}
368	Ok(changed)
369	}
370
371	/// Whether `after` stores as `before` does: the same type and bytes, naming the same
372	/// identities. Stored tables keep only the entries an object names, so those decide.
373	pub(crate) fn unchanged(before: &crate::Object<'_>, after: &crate::Object<'_>) -> Result<bool> {
374	if before.jcid != after.jcid || before.data != after.data {
375	return Ok(false);
376	}
377	let entries = match after.data {
378	ObjectData::Properties(bytes) => table_entries(bytes)?,
379	_ => Vec::new(),
380	};
381	Ok(entries
382	.iter()
383	.all(|entry| before.global_ids.get(entry) == after.global_ids.get(entry)))
384	}
385
386	/// `object` as a replacement a revision stores under `id`.
387	pub(crate) fn replacement(id: ExGuid, object: &crate::Object<'_>) -> Result<PropertyObject> {
388	let mut replacement = match object.data {
389	ObjectData::Properties(_) => PropertyObject::from_object(object)?,
390	ObjectData::File {
391	reference,
392	extension,
393	} => {
394	let text = |bytes: &[u8]| {
395	String::from_utf16(
396	&bytes
397	.chunks_exact(2)
398	.map(|pair| u16::from_le_bytes([pair[0], pair[1]]))
399	.collect::<Vec<_>>(),
400	)
401	.map_err(|_| Error {
402	offset: 0,
403	message: "Invalid UTF-16 file-data declaration",
404	})
405	};
406	let mut replacement = PropertyObject::file(id, &text(reference)?, &text(extension)?)?;
407	replacement.jcid = object.jcid;
408	replacement
409	}
410	ObjectData::Encrypted(_) => {
411	return Err(Error {
412	offset: 0,
413	message: "Page edits only produce property objects",
414	});
415	}
416	};
417	replacement.reference(id)?;
418	Ok(replacement)
419	}
420
421	/// The object type OneNote gives embedded picture payload declarations; embedded files
422	/// use `EMBEDDED_FILE_JCID` with the same declaration shape, and a printout's XPS package
423	/// `PRINTOUT_FILE_JCID` (`corpus/printout`).
424	pub(crate) const FILE_DATA_JCID: u32 = 0x80039;
425	pub(crate) const EMBEDDED_FILE_JCID: u32 = 0x80036;
426	pub(crate) const PRINTOUT_FILE_JCID: u32 = 0x8003a;
427
428	/// The reference and extension of a file-data declaration built by `PropertyObject::file`.
429	fn file_declaration(bytes: &[u8]) -> Result<(&[u8], &[u8])> {
430	let malformed = || Error {
431	offset: 0,
432	message: "Malformed file-data declaration",
433	};
434	let mut rest = bytes;
435	let mut parts = Vec::new();
436	for _ in 0..2 {
437	let length = usize::try_from(u32::from_le_bytes(
438	rest.get(..4).ok_or_else(malformed)?.try_into().unwrap(),
439	))
440	.map_err(|_| malformed())?;
441	let bytes = rest.get(4..4 + length).ok_or_else(malformed)?;
442	parts.push(bytes);
443	rest = &rest[4 + length..];
444	}
445	if !rest.is_empty() {
446	return Err(malformed());
447	}
448	Ok((parts[0], parts[1]))
449	}
450
451	/// An object of type `jcid` stored as `bytes`, as a revision declares it.
452	pub(crate) fn declared(
453	jcid: u32,
454	bytes: &[u8],
455	global_ids: Arc<BTreeMap<u32, [u8; 16]>>,
456	) -> Result<crate::Object<'_>> {
457	let data = if is_file_declaration(jcid) {
458	let (reference, extension) = file_declaration(bytes)?;
459	ObjectData::File {
460	reference,
461	extension,
462	}
463	} else {
464	ObjectData::Properties(bytes)
465	};
466	Ok(crate::Object {
467	jcid,
468	reference_count: 0,
469	data,
470	global_ids,
471	})
472	}
473
474	fn is_file_declaration(jcid: u32) -> bool {
475	matches!(
476	jcid,
477	FILE_DATA_JCID | EMBEDDED_FILE_JCID | PRINTOUT_FILE_JCID
478	)
479	}
480
481	#[derive(Clone)]
482	pub(crate) struct PropertyObject {
483	pub jcid: u32,
484	pub bytes: Vec<u8>,
485	pub global_ids: Arc<BTreeMap<u32, [u8; 16]>>,
486	}
487
488	pub(crate) enum RevisionEdit {
489	Update(BTreeMap<ExGuid, PropertyObject>),
490	#[cfg(test)]
491	Create {
492	roots: BTreeMap<u32, ExGuid>,
493	objects: BTreeMap<ExGuid, PropertyObject>,
494	},
495	}
496
497	impl PropertyObject {
498	/// A file-data object declaring an embedded payload by its store identity, or an
499	/// external payload by name; `extension` includes its leading dot.
500	pub fn file(id: ExGuid, reference: &str, extension: &str) -> Result<Self> {
501	if reference.is_empty() || reference.contains('\0') || extension.contains('\0') {
502	return Err(Error {
503	offset: 0,
504	message: "File-data references and extensions are nonempty and contain no NUL",
505	});
506	}
507	let mut bytes = Vec::new();
508	for text in [reference, extension] {
509	let encoded: Vec<u8> = text.encode_utf16().flat_map(u16::to_le_bytes).collect();
510	bytes.extend_from_slice(&u32::try_from(encoded.len()).unwrap().to_le_bytes());
511	bytes.extend_from_slice(&encoded);
512	}
513	Ok(Self {
514	jcid: FILE_DATA_JCID,
515	bytes,
516	global_ids: Arc::new(BTreeMap::from([(0, id.guid)])),
517	})
518	}
519
520	pub fn from_object(object: &crate::Object<'_>) -> Result<Self> {
521	let ObjectData::Properties(bytes) = object.data else {
522	return Err(Error {
523	offset: 0,
524	message: "Object does not contain editable properties",
525	});
526	};
527	Ok(Self {
528	jcid: object.jcid,
529	bytes: bytes.to_vec(),
530	global_ids: Arc::clone(&object.global_ids),
531	})
532	}
533
534	pub fn set(&mut self, values: &[(u32, &[u8])]) -> Result<()> {
535	let properties = PropertySets::parse(&self.bytes)?;
536	let (updates, inserts): (Vec<_>, Vec<_>) = values.iter().copied().partition(|(id, _)| {
537	properties.sets[0]
538	.iter()
539	.any(|p| p.id & 0x7fffffff == id & 0x7fffffff)
540	});
541	self.bytes = patch_properties(&self.bytes, &updates, &inserts, &[])?;
542	Ok(())
543	}
544
545	/// Replaces a property-set array such as note tags: each set lists scalar values
546	/// inline, while an object reference (a kind-8 identity) is supplied as the compact
547	/// identity `reference` produced and joins the object's reference stream in order.
548	pub fn set_sets(&mut self, id: u32, element: u32, sets: &[Vec<(u32, Vec<u8>)>]) -> Result<()> {
549	if (id >> 26) & 31 != 16 || (element >> 26) & 31 != 17 {
550	return Err(Error {
551	offset: 0,
552	message: "Property-set arrays need array and element identifiers",
553	});
554	}
555	self.remove(&[id])?;
556	if sets.is_empty() {
557	return Ok(());
558	}
559	let mut encoded = (sets.len() as u32).to_le_bytes().to_vec();
560	encoded.extend_from_slice(&element.to_le_bytes());
561	let mut references = Vec::new();
562	for set in sets {
563	encoded.extend_from_slice(&u16::try_from(set.len()).unwrap().to_le_bytes());
564	for (field, _) in set {
565	encoded.extend_from_slice(&field.to_le_bytes());
566	}
567	for (field, value) in set {
568	match (field >> 26) & 31 {
569	3..=6 => {
570	assert_eq!(value.len(), 1 << (((field >> 26) & 31) - 3));
571	encoded.extend_from_slice(value);
572	}
573	7 => {
574	encoded.extend_from_slice(&(value.len() as u32).to_le_bytes());
575	encoded.extend_from_slice(value);
576	}
577	8 => {
578	assert_eq!(value.len(), 4);
579	references.extend_from_slice(value);
580	}
581	_ => {
582	return Err(Error {
583	offset: 0,
584	message: "Property-set arrays hold scalars and single references",
585	});
586	}
587	}
588	}
589	}
590	self.bytes = patch_properties(&self.bytes, &[], &[(id, &encoded)], &references)?;
591	Ok(())
592	}
593
594	pub fn remove(&mut self, ids: &[u32]) -> Result<()> {
595	let properties = PropertySets::parse(&self.bytes)?;
596	let removed = |id: u32| {
597	ids.iter()
598	.any(|wanted| id & 0x7fffffff == wanted & 0x7fffffff)
599	};
600	if !properties.sets[0].iter().any(|p| removed(p.id)) {
601	return Ok(());
602	}
603	let lengths = property_set_lengths(&properties);
604	let mut offset = properties.root_ids.as_ptr().addr() - self.bytes.as_ptr().addr()
605	+ properties.root_ids.len();
606	let mut retained_ids = Vec::new();
607	let mut fields = Vec::new();
608	let mut references: [Vec<u8>; 3] = std::array::from_fn(|_| Vec::new());
609	for property in &properties.sets[0] {
610	let end = offset + field_length(property, &lengths);
611	if !removed(property.id) {
612	retained_ids.extend_from_slice(&property.id.to_le_bytes());
613	fields.extend_from_slice(&self.bytes[offset..end]);
614	let mut pending = vec![property];
615	while let Some(field) = pending.pop() {
616	match &field.value {
617	Value::References {
618	stream,
619	compact_ids,
620	} => {
621	let index = match stream {
622	crate::IdStream::Objects => 0,
623	crate::IdStream::ObjectSpaces => 1,
624	crate::IdStream::Contexts => 2,
625	};
626	references[index].extend_from_slice(compact_ids);
627	}
628	Value::Sets(children) => {
629	for child in children.clone().rev() {
630	pending.extend(properties.sets[child].iter().rev());
631	}
632	}
633	_ => {}
634	}
635	}
636	}
637	offset = end;
638	}
639	let mut cursor = crate::bytes::Cursor {
640	bytes: &self.bytes,
641	offset: 0,
642	};
643	let streams = crate::properties::reference_streams(&mut cursor)?;
644	let mut bytes = Vec::new();
645	for (stream, retained) in streams.iter().zip(&references) {
646	if stream.offset == 0 {
647	continue;
648	}
649	let header = u32::from_le_bytes(
650	self.bytes[stream.offset - 4..stream.offset]
651	.try_into()
652	.unwrap(),
653	);
654	let count = u32::try_from(retained.len() / 4).unwrap();
655	bytes.extend_from_slice(&((header & 0xff000000) | count).to_le_bytes());
656	bytes.extend_from_slice(retained);
657	}
658	bytes.extend_from_slice(&u16::try_from(retained_ids.len() / 4).unwrap().to_le_bytes());
659	bytes.extend_from_slice(&retained_ids);
660	bytes.extend_from_slice(&fields);
661	bytes.resize(bytes.len().next_multiple_of(8), 0);
662	PropertySets::parse(&bytes)?;
663	self.bytes = bytes;
664	Ok(())
665	}
666
667	pub fn reference(&mut self, id: ExGuid) -> Result<[u8; 4]> {
668	if !self.global_ids.values().any(|guid| *guid == id.guid) {
669	let mut index = 0;
670	for key in self.global_ids.keys() {
671	if *key != index {
672	break;
673	}
674	index += 1;
675	}
676	if index >= 0xffffff || id.guid == [0; 16] {
677	return Err(Error {
678	offset: 0,
679	message: "Object identity cannot be added to the global ID table",
680	});
681	}
682	Arc::make_mut(&mut self.global_ids).insert(index, id.guid);
683	}
684	compact(id, &self.global_ids)
685	}
686
687	pub fn copy_property(&mut self, source: &Self, id: u32) -> Result<()> {
688	let properties = PropertySets::parse(&source.bytes)?;
689	let mut target = Self {
690	jcid: self.jcid,
691	bytes: self.bytes.clone(),
692	global_ids: Arc::clone(&self.global_ids),
693	};
694	target.remove(&[id])?;
695	let lengths = property_set_lengths(&properties);
696	let mut offset = properties.root_ids.as_ptr().addr() - source.bytes.as_ptr().addr()
697	+ properties.root_ids.len();
698	let mut selected = None;
699	for property in &properties.sets[0] {
700	let end = offset + field_length(property, &lengths);
701	if property.id & 0x7fffffff == id & 0x7fffffff {
702	selected = Some((property, &source.bytes[offset..end]));
703	break;
704	}
705	offset = end;
706	}
707	if let Some((property, field)) = selected {
708	let mut added: [Vec<u8>; 3] = std::array::from_fn(|_| Vec::new());
709	let mut pending = vec![property];
710	while let Some(property) = pending.pop() {
711	match &property.value {
712	Value::References {
713	stream,
714	compact_ids,
715	} => {
716	let index = match stream {
717	crate::IdStream::Objects => 0,
718	crate::IdStream::ObjectSpaces => 1,
719	crate::IdStream::Contexts => 2,
720	};
721	let mut cursor = crate::bytes::Cursor {
722	bytes: compact_ids,
723	offset: 0,
724	};
725	while !cursor.bytes.is_empty() {
726	let id = cursor.compact(&source.global_ids)?;
727	added[index].extend_from_slice(&target.reference(id)?);
728	}
729	}
730	Value::Sets(children) => {
731	for child in children.clone().rev() {
732	pending.extend(properties.sets[child].iter().rev());
733	}
734	}
735	_ => {}
736	}
737	}
738	let old = PropertySets::parse(&target.bytes)?;
739	let count = u16::try_from(old.sets[0].len() + 1).map_err(|_| Error {
740	offset: 0,
741	message: "Root property count exceeds the format limit",
742	})?;
743	let streams = crate::properties::reference_streams(&mut crate::bytes::Cursor {
744	bytes: &target.bytes,
745	offset: 0,
746	})?;
747	let stream_count = (0..3)
748	.rev()
749	.find(|i| streams[*i].offset != 0 || !added[*i].is_empty())
750	.unwrap()
751	+ 1;
752	let mut bytes = Vec::new();
753	for i in 0..stream_count {
754	let stream = &streams[i];
755	let count = u32::try_from((stream.bytes.len() + added[i].len()) / 4)
756	.ok()
757	.filter(|n| *n <= 0xffffff)
758	.ok_or(Error {
759	offset: 0,
760	message: "Reference stream exceeds the format limit",
761	})?;
762	let reserved = if stream.offset == 0 {
763	0
764	} else {
765	u32::from_le_bytes(
766	target.bytes[stream.offset - 4..stream.offset]
767	.try_into()
768	.unwrap(),
769	) & 0x3f000000
770	};
771	let flags = match (i, stream_count) {
772	(0, 1) => 0x80000000,
773	(0 | 1, 3) => 0x40000000,
774	_ => 0,
775	};
776	bytes.extend_from_slice(&(count | reserved | flags).to_le_bytes());
777	bytes.extend_from_slice(stream.bytes);
778	bytes.extend_from_slice(&added[i]);
779	}
780	bytes.extend_from_slice(&count.to_le_bytes());
781	bytes.extend_from_slice(old.root_ids);
782	bytes.extend_from_slice(&property.id.to_le_bytes());
783	let start =
784	old.root_ids.as_ptr().addr() - target.bytes.as_ptr().addr() + old.root_ids.len();
785	bytes.extend_from_slice(&target.bytes[start..target.bytes.len() - old.padding.len()]);
786	bytes.extend_from_slice(field);
787	bytes.resize(bytes.len().next_multiple_of(8), 0);
788	PropertySets::parse(&bytes)?;
789	target.bytes = bytes;
790	}
791	*self = target;
792	Ok(())
793	}
794	}
795
796	/// A password-protected section's key, under which a writer stores what it appends.
797	pub(crate) trait Protection {
798	/// The stored bytes an object's clear bytes were decoded from.
799	fn stored(&self, clear: &[u8]) -> Option<&[u8]>;
800	fn seal_property(&self, clear: &[u8]) -> Result<Vec<u8>>;
801	fn seal_file(&self, clear: &[u8]) -> Result<Vec<u8>>;
802	fn open_property(&self, stored: &[u8]) -> Result<zeroize::Zeroizing<Vec<u8>>>;
803	fn open_file(&self, stored: &[u8]) -> Result<zeroize::Zeroizing<Vec<u8>>>;
804	/// The encryption data's chunk, which every revision names.
805	fn metadata(&self) -> Chunk;
806	}
807
808	/// The global-ID entries a group of objects declared together uses: each object's own
809	/// and those its properties reference. A section's group stores only these.
810	fn used_entries<'o>(
811	table: &BTreeMap<u32, [u8; 16]>,
812	objects: impl IntoIterator<Item = (ExGuid, &'o crate::Object<'o>)>,
813	) -> Result<Vec<u32>> {
814	let mut used = Vec::new();
815	for (id, object) in objects {
816	used.push(u32::from_le_bytes(compact(id, table)?) >> 8);
817	if let ObjectData::Properties(bytes) = object.data {
818	used.extend(table_entries(bytes)?);
819	}
820	}
821	used.sort_unstable();
822	used.dedup();
823	Ok(used)
824	}
825
826	/// A space's revision as appending a revision and reading it back leaves it.
827	#[derive(Clone)]
828	pub(crate) struct LiveRevision<'a> {
829	pub revision: crate::ResolvedRevision<'a>,
830	/// Incoming references of each object reachable from the roots; a root counts once.
831	incoming: BTreeMap<ExGuid, u32>,
832	/// Reachable read-only property objects by type and content, which identical new
833	/// objects alias.
834	readonly: BTreeMap<u32, BTreeMap<&'a [u8], BTreeSet<ExGuid>>>,
835	/// Revisions in the dependency chain, counted to 512; zero before the first.
836	pub depth: usize,
837	}
838
839	impl<'a> LiveRevision<'a> {
840	pub(crate) fn new(revision: crate::ResolvedRevision<'a>, depth: usize) -> Result<Self> {
841	let incoming = if depth == 0 {
842	BTreeMap::new()
843	} else {
844	revision.checked_counts()?
845	};
846	let mut readonly = BTreeMap::new();
847	for id in incoming.keys() {
848	index(&mut readonly, *id, &revision.objects[id], true);
849	}
850	Ok(Self {
851	revision,
852	incoming,
853	readonly,
854	depth,
855	})
856	}
857
858	pub(crate) fn is_reachable(&self, id: ExGuid) -> bool {
859	self.incoming.contains_key(&id)
860	}
861
862	/// Validates replacements and drops what the revision would not store: new read-only
863	/// objects identical to reachable or earlier ones, whose references move to those, and
864	/// reachable objects that stay as they are.
865	pub(crate) fn prepare(
866	&self,
867	mut replacements: BTreeMap<ExGuid, PropertyObject>,
868	is_section: bool,
869	) -> Result<BTreeMap<ExGuid, PropertyObject>> {
870	let revision = &self.revision;
871	for (id, replacement) in &replacements {
872	if let Some(object) = revision.objects.get(id) {
873	if object.jcid & 0x100000 != 0 {
874	return Err(Error {
875	offset: 0,
876	message: "Read-only object requires a new identity",
877	});
878	}
879	if replacement.jcid != object.jcid
880	|| !matches!(object.data, ObjectData::Properties(_))
881	{
882	return Err(Error {
883	offset: 0,
884	message: "An existing object's type cannot be changed",
885	});
886	}
887	} else if !is_section && replacement.jcid != 0x20001 {
888	return Err(Error {
889	offset: 0,
890	message: "New objects in a table of contents are its entries",
891	});
892	}
893	if replacement.global_ids.keys().any(|i| *i > 0xffffff) {
894	return Err(Error {
895	offset: 0,
896	message: "Invalid property object declaration",
897	});
898	}
899	compact(*id, &replacement.global_ids)?;
900	if is_file_declaration(replacement.jcid) {
901	if !is_section {
902	return Err(Error {
903	offset: 0,
904	message: "File-data objects require a section file",
905	});
906	}
907	file_declaration(&replacement.bytes)?;
908	} else if replacement.jcid & 0x20000 == 0 {
909	return Err(Error {
910	offset: 0,
911	message: "Invalid property object declaration",
912	});
913	} else {
914	PropertySets::parse(&replacement.bytes)?;
915	}
916	}
917	// Native coalescing of duplicate readonly styles can leave dangling references.
918	let mut aliases = BTreeMap::new();
919	for (id, replacement) in &replacements {
920	if revision.objects.contains_key(id)
921	|| replacement.jcid & 0x100000 == 0
922	|| PropertySets::parse(&replacement.bytes)?
923	.sets
924	.iter()
925	.flatten()
926	.any(|p| matches!(p.value, Value::References { .. }))
927	{
928	continue;
929	}
930	let existing = self
931	.readonly
932	.get(&replacement.jcid)
933	.and_then(|contents| contents.get(replacement.bytes.as_slice()))
934	.and_then(|ids| ids.first().copied());
935	let existing = existing.or_else(|| {
936	replacements.range(..id).find_map(|(other, object)| {
937	(object.jcid == replacement.jcid && object.bytes == replacement.bytes)
938	.then_some(*aliases.get(other).unwrap_or(other))
939	})
940	});
941	if let Some(existing) = existing {
942	aliases.insert(*id, existing);
943	}
944	}
945	for id in aliases.keys() {
946	replacements.remove(id);
947	}
948	for object in replacements.values_mut() {
949	if is_file_declaration(object.jcid) {
950	continue;
951	}
952	// The compact IDs this object's table gives aliased identities.
953	let targets: Vec<(u32, ExGuid)> = aliases
954	.iter()
955	.filter(|(id, _)| id.n <= 0xff)
956	.filter_map(|(id, existing)| {
957	let (index, _) = object.global_ids.iter().find(|(_, g)| **g == id.guid)?;
958	Some(((index << 8) | id.n, *existing))
959	})
960	.collect();
961	if targets.is_empty() {
962	continue;
963	}
964	let mut remapped = Vec::new();
965	for property in PropertySets::parse(&object.bytes)?.sets.iter().flatten() {
966	if let Value::References {
967	stream: crate::IdStream::Objects,
968	compact_ids,
969	} = property.value
970	{
971	for bytes in compact_ids.chunks_exact(4) {
972	let raw = u32::from_le_bytes(bytes.try_into().unwrap());
973	if let Some((_, existing)) = targets.iter().find(|(id, _)| *id == raw) {
974	let offset = bytes.as_ptr().addr() - object.bytes.as_ptr().addr();
975	remapped.push((offset, *existing));
976	}
977	}
978	}
979	}
980	for (offset, id) in remapped {
981	let reference = object.reference(id)?;
982	object.bytes[offset..offset + 4].copy_from_slice(&reference);
983	}
984	}
985	// Detached objects must pass the final reachability check even when unchanged. Equal
986	// bytes are the same object when the table entries they name agree: stored tables
987	// keep only those.
988	let mut unchanged = Vec::new();
989	for (id, replacement) in &replacements {
990	if let Some(object) = revision.objects.get(id)
991	&& self.is_reachable(*id)
992	&& object.data == ObjectData::Properties(&replacement.bytes)
993	&& (Arc::ptr_eq(&object.global_ids, &replacement.global_ids)
994	|| table_entries(&replacement.bytes)?.iter().all(|entry| {
995	object.global_ids.get(entry) == replacement.global_ids.get(entry)
996	}))
997	{
998	unchanged.push(*id);
999	}
1000	}
1001	for id in unchanged {
1002	replacements.remove(&id);
1003	}
1004	Ok(replacements)
1005	}
1006
1007	/// Stores prepared replacements as the next revision, which checkpoints when the chain
1008	/// would exceed 512 revisions.
1009	pub(crate) fn commit(
1010	&mut self,
1011	replacements: Vec<(ExGuid, crate::Object<'a>)>,
1012	) -> Result<Commit> {
1013	let mut changed = BTreeSet::new();
1014	// Whether each object whose count may move was reachable before.
1015	let mut touched = BTreeMap::new();
1016	let (mut added, mut removed) = (Vec::new(), Vec::new());
1017	for (id, object) in replacements {
1018	changed.insert(id);
1019	let reachable = self.is_reachable(id);
1020	touched.insert(id, reachable);
1021	if reachable {
1022	moved_references(
1023	&self.revision.objects[&id],
1024	&object,
1025	&mut removed,
1026	&mut added,
1027	)?;
1028	}
1029	self.revision.objects.insert(id, object);
1030	}
1031	let roots: BTreeSet<ExGuid> = self.revision.roots.values().copied().collect();
1032	if roots.len() != self.revision.roots.len() {
1033	return Err(Error {
1034	offset: 0,
1035	message: "Object is the root of multiple roles",
1036	});
1037	}
1038	added.extend(
1039	roots
1040	.into_iter()
1041	.filter(|id| !self.incoming.contains_key(id)),
1042	);
1043	// Attaching before detaching keeps a moved subtree from being walked twice.
1044	while let Some(id) = added.pop() {
1045	let object = self.revision.objects.get(&id).ok_or(Error {
1046	offset: 0,
1047	message: "Reachable object has no declaration",
1048	})?;
1049	let count = self.incoming.entry(id).or_default();
1050	touched.entry(id).or_insert(*count > 0);
1051	*count = count.checked_add(1).ok_or(Error {
1052	offset: 0,
1053	message: "Object reference count overflows",
1054	})?;
1055	if *count == 1 {
1056	added.extend(object.references()?.objects);
1057	index(&mut self.readonly, id, object, true);
1058	}
1059	}
1060	while let Some(id) = removed.pop() {
1061	touched.entry(id).or_insert(true);
1062	let count = self.incoming.get_mut(&id).unwrap();
1063	*count -= 1;
1064	if *count == 0 {
1065	self.incoming.remove(&id);
1066	let object = &self.revision.objects[&id];
1067	removed.extend(object.references()?.objects);
1068	index(&mut self.readonly, id, object, false);
1069	}
1070	}
1071	for (&id, &reachable) in &touched {
1072	let count = self.incoming.get(&id).copied();
1073	if changed.contains(&id) && count.is_none() {
1074	return Err(Error {
1075	offset: 0,
1076	message: "Edited object is not reachable in the resulting revision",
1077	});
1078	}
1079	let object = self.revision.objects.get_mut(&id).unwrap();
1080	if (reachable || count.is_some()) && object.reference_count != count.unwrap_or(0) {
1081	object.reference_count = count.unwrap_or(0);
1082	changed.insert(id);
1083	}
1084	}
1085	// Native cold-open fails on long dependency chains; cap their depth at 512.
1086	let checkpoint = self.depth == 0 || self.depth >= 512;
1087	self.depth = if checkpoint { 1 } else { self.depth + 1 };
1088	Ok(Commit {
1089	checkpoint,
1090	changed,
1091	touched: touched.into_keys().collect(),
1092	})
1093	}
1094
1095	/// Gives the objects a revision declares the id tables reading it back yields: objects
1096	/// sharing a table are declared in one group, which keeps the entries they use.
1097	pub(crate) fn settle(&mut self, declared: impl IntoIterator<Item = ExGuid>) -> Result<()> {
1098	let mut groups = BTreeMap::<_, Vec<_>>::new();
1099	for id in declared {
1100	let table = Arc::clone(&self.revision.objects[&id].global_ids);
1101	groups.entry(table).or_default().push(id);
1102	}
1103	for (table, ids) in groups {
1104	let used = used_entries(
1105	&table,
1106	ids.iter().map(|id| (*id, &self.revision.objects[id])),
1107	)?;
1108	if used.iter().eq(table.keys()) {
1109	continue;
1110	}
1111	let kept: Arc<BTreeMap<_, _>> = Arc::new(
1112	table
1113	.iter()
1114	.filter(|(entry, _)| used.binary_search(entry).is_ok())
1115	.map(|(entry, guid)| (*entry, *guid))
1116	.collect(),
1117	);
1118	for id in ids {
1119	self.revision.objects.get_mut(&id).unwrap().global_ids = Arc::clone(&kept);
1120	}
1121	}
1122	Ok(())
1123	}
1124	}
1125
1126	/// Adds a reachable read-only property object to `readonly`, or removes an unreachable one.
1127	fn index<'a>(
1128	readonly: &mut BTreeMap<u32, BTreeMap<&'a [u8], BTreeSet<ExGuid>>>,
1129	id: ExGuid,
1130	object: &crate::Object<'a>,
1131	reachable: bool,
1132	) {
1133	let ObjectData::Properties(bytes) = object.data else {
1134	return;
1135	};
1136	if object.jcid & 0x100000 == 0 {
1137	return;
1138	}
1139	let ids = readonly
1140	.entry(object.jcid)
1141	.or_default()
1142	.entry(bytes)
1143	.or_default();
1144	if reachable {
1145	ids.insert(id);
1146	} else {
1147	ids.remove(&id);
1148	}
1149	}
1150
1151	/// Adds the object references `before` has and `after`, a later version of the object,
1152	/// lacks to `removed`, and those it gains to `added`.
1153	fn moved_references(
1154	before: &crate::Object<'_>,
1155	after: &crate::Object<'_>,
1156	removed: &mut Vec<ExGuid>,
1157	added: &mut Vec<ExGuid>,
1158	) -> Result<()> {
1159	let compact_ids = |object: &crate::Object<'_>| -> Result<Vec<[u8; 4]>> {
1160	let ObjectData::Properties(bytes) = object.data else {
1161	return Ok(Vec::new());
1162	};
1163	let mut ids = Vec::new();
1164	for property in PropertySets::parse(bytes)?.sets.iter().flatten() {
1165	if let Value::References {
1166	stream: crate::IdStream::Objects,
1167	compact_ids,
1168	} = property.value
1169	{
1170	ids.extend(
1171	compact_ids
1172	.chunks_exact(4)
1173	.map(|id| <[u8; 4]>::try_from(id).unwrap()),
1174	);
1175	}
1176	}
1177	Ok(ids)
1178	};
1179	let decode = |ids: &[[u8; 4]], table| -> Result<Vec<ExGuid>> {
1180	let bytes = ids.concat();
1181	let mut cursor = crate::bytes::Cursor {
1182	bytes: &bytes,
1183	offset: 0,
1184	};
1185	std::iter::from_fn(|| (!cursor.bytes.is_empty()).then(|| cursor.compact(table))).collect()
1186	};
1187	// Equal compact IDs name the same objects where the later table keeps the earlier entries.
1188	let (old, new) = (&before.global_ids, &after.global_ids);
1189	let extended = Arc::ptr_eq(old, new) || {
1190	let mut later = new.iter();
1191	old.iter()
1192	.all(|entry| later.find(|later| later.0 >= entry.0) == Some(entry))
1193	};
1194	if extended {
1195	let (old_ids, new_ids) = (compact_ids(before)?, compact_ids(after)?);
1196	let (gone, gained) = differing(&old_ids, &new_ids);
1197	removed.extend(decode(gone, old)?);
1198	added.extend(decode(gained, new)?);
1199	} else {
1200	let (old_refs, new_refs) = (before.references()?.objects, after.references()?.objects);
1201	let (gone, gained) = differing(&old_refs, &new_refs);
1202	removed.extend_from_slice(gone);
1203	added.extend_from_slice(gained);
1204	}
1205	Ok(())
1206	}
1207
1208	/// The parts of two sequences between their common prefix and suffix: removing the first
1209	/// from `before` and adding the second yields `after` as a multiset.
1210	pub(crate) fn differing<'s, T: PartialEq>(before: &'s [T], after: &'s [T]) -> (&'s [T], &'s [T]) {
1211	let prefix = before.iter().zip(after).take_while(|(a, b)| a == b).count();
1212	let suffix = before[prefix..]
1213	.iter()
1214	.rev()
1215	.zip(after[prefix..].iter().rev())
1216	.take_while(|(a, b)| a == b)
1217	.count();
1218	(
1219	&before[prefix..before.len() - suffix],
1220	&after[prefix..after.len() - suffix],
1221	)
1222	}
1223
1224	/// A revision `LiveRevision::commit` stored.
1225	#[derive(Clone)]
1226	pub(crate) struct Commit {
1227	/// Whether the revision declares every object, depending on none.
1228	pub checkpoint: bool,
1229	/// The objects it declares otherwise: the replacements and those whose counts moved.
1230	pub changed: BTreeSet<ExGuid>,
1231	/// Objects whose reachability or reference count may have moved.
1232	pub touched: BTreeSet<ExGuid>,
1233	}
1234
1235	/// Revisions in the dependency chain of `rid`, counted to 512.
1236	pub(crate) fn chain_depth(index: &RevisionIndex<'_>, space: ExGuid, rid: ExGuid) -> usize {
1237	std::iter::successors(Some(rid), |id| {
1238	index.spaces[&space].revisions[id].dependency
1239	})
1240	.take(512)
1241	.count()
1242	}
1243
1244	/// A test fixture: `source` with one revision of `space` storing `edit`'s objects.
1245	#[cfg(test)]
1246	pub(crate) fn write_revision(
1247	source: &[u8],
1248	space: ExGuid,
1249	edit: impl FnOnce(&crate::ResolvedRevision<'_>) -> Result<BTreeMap<ExGuid, PropertyObject>>,
1250	) -> Result<Vec<u8>> {
1251	write_revisions(source, update(space, edit))
1252	}
1253
1254	/// One space's active revision edited into its update.
1255	#[cfg(test)]
1256	fn update(
1257	space: ExGuid,
1258	edit: impl FnOnce(&crate::ResolvedRevision<'_>) -> Result<BTreeMap<ExGuid, PropertyObject>>,
1259	) -> impl FnOnce(&RevisionIndex<'_>) -> Result<BTreeMap<ExGuid, RevisionEdit>> {
1260	move |index| {
1261	let revision = index.resolve(space, index.active(space)?)?;
1262	Ok(BTreeMap::from([(
1263	space,
1264	RevisionEdit::Update(edit(&revision)?),
1265	)]))
1266	}
1267	}
1268
1269	/// A test fixture: the transaction appending `edit`'s revisions to `source`.
1270	#[cfg(test)]
1271	pub(crate) fn revisions(
1272	source: &[u8],
1273	edit: impl FnOnce(&RevisionIndex<'_>) -> Result<BTreeMap<ExGuid, RevisionEdit>>,
1274	) -> Result<Option<crate::Transaction>> {
1275	let store = Store::parse(source)?;
1276	let index = RevisionIndex::parse(&store)?;
1277	index.validate_current()?;
1278	build_on(&index, &[], edit)
1279	}
1280
1281	/// A test fixture: `source` with `edit`'s revisions appended.
1282	#[cfg(test)]
1283	pub(crate) fn write_revisions(
1284	source: &[u8],
1285	edit: impl FnOnce(&RevisionIndex<'_>) -> Result<BTreeMap<ExGuid, RevisionEdit>>,
1286	) -> Result<Vec<u8>> {
1287	publish(source, true, edit)
1288	}
1289
1290	#[cfg(test)]
1291	fn publish(
1292	source: &[u8],
1293	validate: bool,
1294	edit: impl FnOnce(&RevisionIndex<'_>) -> Result<BTreeMap<ExGuid, RevisionEdit>>,
1295	) -> Result<Vec<u8>> {
1296	// The parsed source is released before the result is parsed.
1297	let output = build(source, validate, edit)?;
1298	check(&output, validate)?;
1299	Ok(output)
1300	}
1301
1302	/// Parses a written image, and with `validate` requires its current revisions complete.
1303	pub(crate) fn check(output: &[u8], validate: bool) -> Result<()> {
1304	let store = Store::parse(output)?;
1305	let index = RevisionIndex::parse(&store)?;
1306	if validate {
1307	index.validate_current()?;
1308	}
1309	Ok(())
1310	}
1311
1312	/// The written image, unchecked: `check` follows once the caller has released whatever
1313	/// `edit` borrowed.
1314	#[cfg(test)]
1315	fn build(
1316	source: &[u8],
1317	validate: bool,
1318	edit: impl FnOnce(&RevisionIndex<'_>) -> Result<BTreeMap<ExGuid, RevisionEdit>>,
1319	) -> Result<Vec<u8>> {
1320	let store = Store::parse(source)?;
1321	let index = RevisionIndex::parse(&store)?;
1322	if validate {
1323	index.validate_current()?;
1324	}
1325	applied(source, build_on(&index, &[], edit)?.as_ref())
1326	}
1327
1328	/// `write_revision` on a source the caller has parsed and validated.
1329	#[cfg(test)]
1330	pub(crate) fn write_revision_on(
1331	index: &RevisionIndex<'_>,
1332	space: ExGuid,
1333	edit: impl FnOnce(&crate::ResolvedRevision<'_>) -> Result<BTreeMap<ExGuid, PropertyObject>>,
1334	) -> Result<Vec<u8>> {
1335	let output = applied(
1336	index.store.data,
1337	build_on(index, &[], update(space, edit))?.as_ref(),
1338	)?;
1339	check(&output, true)?;
1340	Ok(output)
1341	}
1342
1343	#[cfg(test)]
1344	thread_local! {
1345	/// Revisions `build_on` has built on this thread.
1346	pub(crate) static BUILDS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
1347	}
1348
1349	/// The transaction appending `edit`'s revisions and the `payloads` to the parsed store;
1350	/// none when nothing changes.
1351	pub(crate) fn build_on(
1352	index: &RevisionIndex<'_>,
1353	payloads: &[([u8; 16], &[u8])],
1354	edit: impl FnOnce(&RevisionIndex<'_>) -> Result<BTreeMap<ExGuid, RevisionEdit>>,
1355	) -> Result<Option<crate::Transaction>> {
1356	#[cfg(test)]
1357	BUILDS.with(|builds| builds.set(builds.get() + 1));
1358	let store = index.store;
1359	let source = store.data;
1360	let is_section = store.header.file_type == FileType::Section;
1361	if !store.checksum_mismatches.is_empty() {
1362	return Err(Error {
1363	offset: store.checksum_mismatches[0],
1364	message: "Cannot write a file with transaction checksum damage",
1365	});
1366	}
1367	let changes = edit(index)?;
1368	let mut appending = Appending::new(store.state()?);
1369	for (space, change) in changes {
1370	let current = (ExGuid::default(), 1_u32);
1371	let (rid, label, revision, replacements, new_space) = match change {
1372	RevisionEdit::Update(objects) => {
1373	let rid = index.active(space)?;
1374	(
1375	Some(rid),
1376	current,
1377	index.resolve(space, rid)?,
1378	objects,
1379	false,
1380	)
1381	}
1382	#[cfg(test)]
1383	RevisionEdit::Create { roots, objects } => {
1384	if !is_section || space.guid == [0; 16] || index.spaces.contains_key(&space) {
1385	return Err(Error {
1386	offset: 0,
1387	message: "Choose a new object-space identity in a section file",
1388	});
1389	}
1390	if roots.is_empty() || objects.is_empty() {
1391	return Err(Error {
1392	offset: 0,
1393	message: "New object space needs roots and objects",
1394	});
1395	}
1396	(
1397	None,
1398	current,
1399	crate::ResolvedRevision {
1400	roots,
1401	objects: BTreeMap::new(),
1402	},
1403	objects,
1404	true,
1405	)
1406	}
1407	};
1408	let depth = rid.map_or(0, |rid| chain_depth(index, space, rid));
1409	let mut live = LiveRevision::new(revision, depth)?;
1410	let replacements = live.prepare(replacements, is_section)?;
1411	if replacements.is_empty() {
1412	continue;
1413	}
1414	let replaced: BTreeSet<ExGuid> = replacements.keys().copied().collect();
1415	let created = replaced
1416	.iter()
1417	.filter(|id| !live.revision.objects.contains_key(id))
1418	.copied()
1419	.collect();
1420	let commit = live.commit(
1421	replacements
1422	.iter()
1423	.map(|(id, replacement)| {
1424	let global_ids = Arc::clone(&replacement.global_ids);
1425	Ok((
1426	*id,
1427	declared(replacement.jcid, &replacement.bytes, global_ids)?,
1428	))
1429	})
1430	.collect::<Result<Vec<_>>>()?,
1431	)?;
1432	appending.revision(
1433	&Sealing {
1434	space,
1435	previous: rid,
1436	new_space,
1437	label,
1438	rid: None,
1439	live: &live,
1440	commit: &commit,
1441	replaced: &replaced,
1442	created: &created,
1443	},
1444	&[(0, source)],
1445	None,
1446	)?;
1447	}
1448	appending.payloads(payloads, None)?;
1449	Ok(appending.finish()?.map(|(transaction, _)| transaction))
1450	}
1451
1452	/// `source` with `transaction` applied.
1453	pub(crate) fn applied(source: &[u8], transaction: Option<&crate::Transaction>) -> Result<Vec<u8>> {
1454	let mut output = source.to_vec();
1455	if let Some(transaction) = transaction {
1456	transaction.apply(&mut output)?;
1457	}
1458	Ok(output)
1459	}
1460
1461	/// Payload identities the file-data store of `store` declares, in order.
1462	pub(crate) fn declared_payloads(store: &Store<'_>) -> Vec<[u8; 16]> {
1463	store
1464	.lists
1465	.values()
1466	.flat_map(|list| &list.nodes)
1467	.filter(|node| node.id == 0x94 && !node.freed())
1468	.filter_map(|node| node.payload.get(..16).and_then(|g| g.try_into().ok()))
1469	.collect()
1470	}
1471
1472	/// Writes the live objects of each `edited` revision that differ from its space's active
1473	/// revision in the validated `source` as one revision per space, embedding the `payloads`
1474	/// it lacks.
1475	#[cfg(test)]
1476	pub(crate) fn squash(
1477	source: &RevisionIndex<'_>,
1478	edited: &[(ExGuid, &crate::ResolvedRevision<'_>)],
1479	payloads: &[([u8; 16], &[u8])],
1480	) -> Result<Option<crate::Transaction>> {
1481	let existing = declared_payloads(source.store);
1482	let payloads: Vec<_> = payloads
1483	.iter()
1484	.filter(|(guid, _)| !existing.contains(guid))
1485	.copied()
1486	.collect();
1487	build_on(source, &payloads, |index| {
1488	let mut changes = BTreeMap::new();
1489	for (space, after) in edited {
1490	let before = index.resolve_active(*space)?;
1491	if before.roots != after.roots {
1492	return Err(Error {
1493	offset: 0,
1494	message: "Page edits cannot change revision roots",
1495	});
1496	}
1497	// Retired styles and deleted content stay in history; only live objects are written.
1498	let live = after.reachable()?;
1499	let mut changed = BTreeMap::new();
1500	for (id, object) in &after.objects {
1501	if !live.contains(id)
1502	|| before
1503	.objects
1504	.get(id)
1505	.map(|previous| unchanged(previous, object))
1506	.transpose()?
1507	== Some(true)
1508	{
1509	continue;
1510	}
1511	changed.insert(*id, replacement(*id, object)?);
1512	}
1513	changes.insert(*space, RevisionEdit::Update(changed));
1514	}
1515	Ok(changes)
1516	})
1517	}
1518
1519	/// A whole revision for `rewrite`, with the labels it is current under.
1520	pub(crate) struct Labelled<'a> {
1521	pub labels: Vec<(ExGuid, u32)>,
1522	pub revision: crate::ResolvedRevision<'a>,
1523	}
1524
1525	/// `skeleton` (`create::skeleton`) with `spaces` appended, each revision a checkpoint under
1526	/// its labels, and `payloads`, all stored under `key` when one is given.
1527	pub(crate) fn rewrite(
1528	skeleton: Vec<u8>,
1529	spaces: &[(ExGuid, Vec<Labelled<'_>>)],
1530	payloads: &[([u8; 16], &[u8])],
1531	key: Option<&crate::protected::Key>,
1532	) -> Result<Vec<u8>> {
1533	let store = Store::parse(&skeleton)?;
1534	let state = store.state()?;
1535	let declared: BTreeSet<ExGuid> = state.spaces.keys().copied().collect();
1536	let mut appending = Appending::new(state);
1537	let opened = key
1538	.map(|key| -> Result<_> {
1539	let mut container = 0xfb6ba385dad1a067_u64.to_le_bytes().to_vec();
1540	container.extend_from_slice(key.metadata());
1541	container.extend_from_slice(&0x2649294f8e198b3c_u64.to_le_bytes());
1542	Ok(crate::protected::Opened::sealing(
1543	key,
1544	appending.append(&container)?,
1545	))
1546	})
1547	.transpose()?;
1548	let protection = opened.as_ref().map(|opened| opened as &dyn Protection);
1549	for (space, revisions) in spaces {
1550	let new = !declared.contains(space);
1551	let mut manifest = Vec::new();
1552	let mut labels = Vec::new();
1553	for (
1554	index,
1555	Labelled {
1556	labels: names,
1557	revision,
1558	},
1559	) in revisions.iter().enumerate()
1560	{
1561	let mut live = LiveRevision::new(
1562	crate::ResolvedRevision {
1563	roots: revision.roots.clone(),
1564	objects: BTreeMap::new(),
1565	},
1566	0,
1567	)?;
1568	let commit = live.commit(
1569	revision
1570	.objects
1571	.iter()
1572	.map(|(id, object)| {
1573	let mut object = object.clone();
1574	object.reference_count = 0;
1575	(*id, object)
1576	})
1577	.collect(),
1578	)?;
1579	let all: BTreeSet<ExGuid> = live.revision.objects.keys().copied().collect();
1580	let (first, others) = names.split_first().ok_or(Error {
1581	offset: 0,
1582	message: "A rewritten revision needs a label",
1583	})?;
1584	let (rid, _) = appending.manifest(
1585	&Sealing {
1586	space: *space,
1587	previous: None,
1588	new_space: new && index == 0,
1589	label: *first,
1590	rid: None,
1591	live: &live,
1592	commit: &commit,
1593	replaced: &all,
1594	created: &all,
1595	},
1596	&[],
1597	protection,
1598	&mut manifest,
1599	)?;
1600	for (context, role) in others {
1601	let mut payload = Vec::new();
1602	rid.encode(&mut payload);
1603	payload.extend_from_slice(&role.to_le_bytes());
1604	let id = if *context == ExGuid::default() {
1605	0x5c
1606	} else {
1607	context.encode(&mut payload);
1608	0x5d
1609	};
1610	labels.push(node(id, None, &payload)?);
1611	}
1612	}
1613	manifest.extend(labels);
1614	appending.close(*space, new, &manifest)?;
1615	}
1616	appending.payloads(payloads, protection)?;
1617	let (transaction, _) = appending.finish()?.ok_or(Error {
1618	offset: 0,
1619	message: "A rewritten section holds nothing",
1620	})?;
1621	applied(&skeleton, Some(&transaction))
1622	}
1623
1624	/// A space's revision as `LiveRevision::commit` left it, ready to append.
1625	pub(crate) struct Sealing<'r, 'a> {
1626	pub space: ExGuid,
1627	/// The revision it depends on unless it is a checkpoint; none for a new space or label.
1628	pub previous: Option<ExGuid>,
1629	pub new_space: bool,
1630	/// The context and role it is current under.
1631	pub label: (ExGuid, u32),
1632	/// Its identity, where the caller chose one; a fresh one otherwise.
1633	pub rid: Option<ExGuid>,
1634	pub live: &'r LiveRevision<'a>,
1635	pub commit: &'r Commit,
1636	/// Objects whose bytes the revision stores rather than referencing stored bytes.
1637	pub replaced: &'r BTreeSet<ExGuid>,
1638	/// Replaced objects the space did not hold before.
1639	pub created: &'r BTreeSet<ExGuid>,
1640	}
1641
1642	/// The chunk `bytes` occupies in a store whose bytes `segments` hold at their offsets.
1643	fn located(segments: &[(u64, &[u8])], bytes: &[u8]) -> Result<Chunk> {
1644	let address = bytes.as_ptr().addr();
1645	segments
1646	.iter()
1647	.find_map(|(offset, segment)| {
1648	let start = address.checked_sub(segment.as_ptr().addr())?;
1649	(start + bytes.len() <= segment.len()).then(|| Chunk {
1650	offset: offset + start as u64,
1651	length: bytes.len() as u64,
1652	})
1653	})
1654	.ok_or(Error {
1655	offset: 0,
1656	message: "Stored object data lies outside the store",
1657	})
1658	}
1659
1660	/// A transaction under construction: bytes appended at the end of a store and patches
1661	/// inside it, advancing `state` as its lists grow.
1662	pub(crate) struct Appending {
1663	pub state: StoreState,
1664	base: crate::Stamp,
1665	append: Vec<u8>,
1666	patches: Vec<(u64, Vec<u8>)>,
1667	/// File-node counts of the lists this transaction writes, as log entries.
1668	counts: Vec<(u32, usize)>,
1669	/// Nodes the root list gains: new object spaces and the file-data store.
1670	root_nodes: Vec<Vec<u8>>,
1671	}
1672
1673	impl Appending {
1674	pub(crate) fn new(state: StoreState) -> Self {
1675	let base = state.stamp.clone();
1676	let mut append = Vec::with_capacity(1 << 16);
1677	// Native files reserve 1 KiB per transaction-log fragment; a fragment that ends the
1678	// file keeps that room before the first new chunk.
1679	let (tail, _) = state.log;
1680	if (tail.offset + tail.length).next_multiple_of(8) >= base.length {
1681	let reserved = tail.offset + tail.length.max(1024) + 32;
1682	append.resize(reserved.saturating_sub(base.length) as usize, 0);
1683	}
1684	Self {
1685	state,
1686	base,
1687	append,
1688	patches: Vec::new(),
1689	counts: Vec::new(),
1690	root_nodes: Vec::new(),
1691	}
1692	}
1693
1694	fn end(&self) -> u64 {
1695	self.base.length + self.append.len() as u64
1696	}
1697
1698	pub(crate) fn append(&mut self, bytes: &[u8]) -> Result<Chunk> {
1699	let length = u64::from(u32::try_from(bytes.len()).map_err(|_| Error {
1700	offset: 0,
1701	message: "Chunk exceeds the encoded length limit",
1702	})?);
1703	let padding = self.end().next_multiple_of(8) - self.end();
1704	self.append.resize(self.append.len() + padding as usize, 0);
1705	let offset = self.end();
1706	self.append.extend_from_slice(bytes);
1707	Ok(Chunk { offset, length })
1708	}
1709
1710	/// Writes `bytes` at a file offset: into the appended bytes, or as a patch.
1711	fn write(&mut self, offset: u64, bytes: &[u8]) {
1712	match offset.checked_sub(self.base.length) {
1713	Some(at) => {
1714	let at = at as usize;
1715	self.append[at..at + bytes.len()].copy_from_slice(bytes);
1716	}
1717	None => self.patches.push((offset, bytes.to_vec())),
1718	}
1719	}
1720
1721	fn allocate_list(&mut self) -> Result<u32> {
1722	self.state.max_list = self.state.max_list.checked_add(1).ok_or(Error {
1723	offset: 0,
1724	message: "File-node list identities are exhausted",
1725	})?;
1726	Ok(self.state.max_list)
1727	}
1728
1729	/// Appends `nodes` as a new list.
1730	fn list(&mut self, nodes: &[Vec<u8>]) -> Result<(Chunk, ListTail)> {
1731	let id = self.allocate_list()?;
1732	let chunk = self.append(&fragment(id, 0, nodes))?;
1733	self.counts.push((id, nodes.len()));
1734	Ok((
1735	chunk,
1736	ListTail {
1737	id,
1738	fragments: 1,
1739	last: chunk,
1740	nodes: nodes.len(),
1741	end: chunk.offset + 16 + nodes.iter().map(Vec::len).sum::<usize>() as u64,
1742	},
1743	))
1744	}
1745
1746	/// Appends `nodes` to the list ending at `tail` as its next fragment.
1747	fn extend(&mut self, tail: &mut ListTail, nodes: &[Vec<u8>]) -> Result<()> {
1748	let chunk = self.append(&fragment(tail.id, tail.fragments, nodes))?;
1749	let next = tail.last.offset + tail.last.length - 20;
1750	if next - tail.end >= 4 {
1751	self.write(tail.end, &node(0xff, None, &[])?);
1752	}
1753	let mut reference = chunk.offset.to_le_bytes().to_vec();
1754	reference.extend_from_slice(&(chunk.length as u32).to_le_bytes());
1755	self.write(next, &reference);
1756	*tail = ListTail {
1757	id: tail.id,
1758	fragments: tail.fragments.checked_add(1).ok_or(Error {
1759	offset: 0,
1760	message: "File-node fragment sequences are exhausted",
1761	})?,
1762	last: chunk,
1763	nodes: tail.nodes + nodes.len(),
1764	end: chunk.offset + 16 + nodes.iter().map(Vec::len).sum::<usize>() as u64,
1765	};
1766	self.counts.push((tail.id, tail.nodes));
1767	Ok(())
1768	}
1769
1770	/// Appends a space's next revision: its manifest, object groups and new data. Returns the
1771	/// revision's identity and where it stored each replaced object's bytes.
1772	pub(crate) fn revision(
1773	&mut self,
1774	sealing: &Sealing<'_, '_>,
1775	segments: &[(u64, &[u8])],
1776	protection: Option<&dyn Protection>,
1777	) -> Result<(ExGuid, Vec<(ExGuid, Chunk)>)> {
1778	let mut manifest = Vec::new();
1779	let written = self.manifest(sealing, segments, protection, &mut manifest)?;
1780	self.close(sealing.space, sealing.new_space, &manifest)?;
1781	Ok(written)
1782	}
1783
1784	/// Appends a revision's object groups and new data, and its manifest's nodes to
1785	/// `manifest` for `close`; returns its identity and where it stored each replaced
1786	/// object's bytes.
1787	pub(crate) fn manifest(
1788	&mut self,
1789	sealing: &Sealing<'_, '_>,
1790	segments: &[(u64, &[u8])],
1791	protection: Option<&dyn Protection>,
1792	manifest: &mut Vec<Vec<u8>>,
1793	) -> Result<(ExGuid, Vec<(ExGuid, Chunk)>)> {
1794	let is_section = self.state.file_type == FileType::Section;
1795	let Sealing {
1796	space,
1797	label,
1798	live,
1799	commit,
1800	..
1801	} = *sealing;
1802	let revision = &live.revision;
1803	let checkpoint = commit.checkpoint;
1804	let selected: Vec<(&ExGuid, &crate::Object<'_>)> = if checkpoint {
1805	revision.objects.iter().collect()
1806	} else {
1807	commit
1808	.changed
1809	.iter()
1810	.map(|id| (id, &revision.objects[id]))
1811	.collect()
1812	};
1813	// A table-of-contents manifest has one global id table (sections group objects,
1814	// each group with its own table); OneNote resolves every node against it.
1815	let toc_table = if is_section {
1816	None
1817	} else {
1818	if checkpoint
1819	&& selected.iter().any(|(_, object)| {
1820	object.jcid != 0x20001 || !matches!(object.data, ObjectData::Properties(_))
1821	})
1822	{
1823	return Err(Error {
1824	offset: 0,
1825	message: "TOC checkpoint requires table-of-contents property objects",
1826	});
1827	}
1828	let guids: BTreeSet<_> = selected
1829	.iter()
1830	.flat_map(|(_, object)| object.global_ids.values().copied())
1831	.collect();
1832	if guids.len() > 0x1000000 {
1833	return Err(Error {
1834	offset: 0,
1835	message: "Global ID table exceeds CompactID capacity",
1836	});
1837	}
1838	Some(
1839	guids
1840	.into_iter()
1841	.enumerate()
1842	.map(|(i, guid)| (u32::try_from(i).unwrap(), guid))
1843	.collect::<BTreeMap<_, _>>(),
1844	)
1845	};
1846	let mut groups = BTreeMap::<_, Vec<_>>::new();
1847	for (id, object) in selected {
1848	groups
1849	.entry(toc_table.as_ref().unwrap_or(&object.global_ids))
1850	.or_default()
1851	.push((*id, object));
1852	}
1853	let new_rid = match sealing.rid {
1854	Some(rid) => rid,
1855	None => ExGuid {
1856	guid: fresh_guid()?,
1857	n: 1,
1858	},
1859	};
1860	let mut start = Vec::new();
1861	new_rid.encode(&mut start);
1862	if checkpoint {
1863	ExGuid::default()
1864	} else {
1865	sealing.previous.ok_or(Error {
1866	offset: 0,
1867	message: "A dependent revision needs the revision it follows",
1868	})?
1869	}
1870	.encode(&mut start);
1871	if !is_section {
1872	start.extend_from_slice(&0_u64.to_le_bytes());
1873	}
1874	start.extend_from_slice(&label.1.to_le_bytes());
1875	start.extend_from_slice(&(if protection.is_some() { 2_u16 } else { 0 }).to_le_bytes());
1876	let contextual = label.0 != ExGuid::default();
1877	if contextual {
1878	label.0.encode(&mut start);
1879	}
1880	if sealing.new_space {
1881	let mut payload = Vec::new();
1882	space.encode(&mut payload);
1883	payload.extend_from_slice(&0_u32.to_le_bytes());
1884	manifest.push(node(0x14, None, &payload)?);
1885	}
1886	manifest.push(node(
1887	match (is_section, contextual) {
1888	(true, true) => 0x1f,
1889	(true, false) => 0x1e,
1890	(false, _) => 0x1b,
1891	},
1892	None,
1893	&start,
1894	)?);
1895	// MS-ONESTORE 2.5.19 has every revision of a protected space name its key; OneNote
1896	// names it only in revisions without a dependency, and reads either.
1897	if let Some(protection) = protection {
1898	manifest.push(node(
1899	0x7c,
1900	Some(Reference::Data(protection.metadata())),
1901	&[],
1902	)?);
1903	}
1904	let mut stored = Vec::new();
1905	for (table, objects) in groups {
1906	let mut payload = Vec::new();
1907	let mut group = if is_section {
1908	ExGuid {
1909	guid: fresh_guid()?,
1910	n: 1,
1911	}
1912	.encode(&mut payload);
1913	vec![node(0xb4, None, &payload)?, node(0x22, None, &[])?]
1914	} else {
1915	vec![node(0x21, None, &[0])?]
1916	};
1917	// A table read from a long-lived page names every session that edited it; the
1918	// group stores the entries its objects use.
1919	let used = used_entries(table, objects.iter().copied())?;
1920	for (id, guid) in table {
1921	if is_section && used.binary_search(id).is_err() {
1922	continue;
1923	}
1924	let mut entry = id.to_le_bytes().to_vec();
1925	entry.extend_from_slice(guid);
1926	group.push(node(0x24, None, &entry)?);
1927	}
1928	group.push(node(0x28, None, &[])?);
1929	let mut override_crc = u32::MAX;
1930	for (id, object) in objects {
1931	let mut declaration = compact(id, table)?.to_vec();
1932	override_crc = crc(
1933	override_crc,
1934	&object.reference_count.to_le_bytes(),
1935	FileType::Section,
1936	);
1937	match object.data {
1938	ObjectData::File {
1939	reference,
1940	extension,
1941	} => {
1942	declaration.extend_from_slice(&object.jcid.to_le_bytes());
1943	declaration.extend_from_slice(&object.reference_count.to_le_bytes());
1944	for bytes in [reference, extension] {
1945	declaration.extend_from_slice(
1946	&u32::try_from(bytes.len() / 2).unwrap().to_le_bytes(),
1947	);
1948	declaration.extend_from_slice(bytes);
1949	}
1950	group.push(node(0x73, None, &declaration)?);
1951	}
1952	ObjectData::Properties(bytes) => {
1953	let references = object.references()?;
1954	let flags = u8::from(!references.objects.is_empty())
1955	| (u8::from(
1956	!references.object_spaces.is_empty()
1957	|| !references.contexts.is_empty(),
1958	) << 1);
1959	let data = if toc_table.is_some() {
1960	let mut mapped = bytes.to_vec();
1961	for property in PropertySets::parse(bytes)?.sets.iter().flatten() {
1962	if let Value::References { compact_ids, .. } = property.value {
1963	let offset =
1964	compact_ids.as_ptr().addr() - bytes.as_ptr().addr();
1965	for (i, value) in compact_ids.chunks_exact(4).enumerate() {
1966	let value = u32::from_le_bytes(value.try_into().unwrap());
1967	let target = ExGuid {
1968	guid: object.global_ids[&(value >> 8)],
1969	n: value & 255,
1970	};
1971	mapped[offset + i * 4..offset + i * 4 + 4]
1972	.copy_from_slice(&compact(target, table)?);
1973	}
1974	}
1975	}
1976	self.append(&mapped)?
1977	} else if sealing.replaced.contains(&id) {
1978	let chunk = match protection {
1979	Some(protection) => {
1980	self.append(&protection.seal_property(bytes)?)?
1981	}
1982	None => self.append(bytes)?,
1983	};
1984	stored.push((id, chunk));
1985	chunk
1986	} else {
1987	located(
1988	segments,
1989	match protection {
1990	Some(protection) => protection.stored(bytes).ok_or(Error {
1991	offset: 0,
1992	message: "Protected object has no stored form",
1993	})?,
1994	None => bytes,
1995	},
1996	)?
1997	};
1998	// A table-of-contents object is declared when the revision is a
1999	// checkpoint or the object is new, and revised otherwise.
2000	let declared = checkpoint || sealing.created.contains(&id);
2001	if is_section {
2002	declaration.extend_from_slice(&object.jcid.to_le_bytes());
2003	declaration.push(flags);
2004	} else if declared {
2005	let body = 1_u64 | (u64::from(flags & 1) << 16);
2006	declaration.extend_from_slice(&body.to_le_bytes()[..6]);
2007	} else {
2008	declaration.extend_from_slice(&u32::from(flags).to_le_bytes());
2009	}
2010	declaration.extend_from_slice(&object.reference_count.to_le_bytes());
2011	let readonly = object.jcid & 0x100000 != 0;
2012	if readonly {
2013	// A protected declaration hashes the plaintext as aligned.
2014	let mut hash = md5::Context::new();
2015	hash.consume(bytes);
2016	if protection.is_some() {
2017	hash.consume(&[0; 7][..(8 - bytes.len() % 8) % 8]);
2018	}
2019	declaration.extend_from_slice(&hash.finalize().0);
2020	}
2021	group.push(node(
2022	if is_section {
2023	if readonly { 0xc5 } else { 0xa5 }
2024	} else if declared {
2025	0x2e
2026	} else {
2027	0x42
2028	},
2029	Some(Reference::Data(data)),
2030	&declaration,
2031	)?);
2032	}
2033	ObjectData::Encrypted(_) => {
2034	return Err(Error {
2035	offset: 0,
2036	message: "Encrypted objects cannot be checkpointed",
2037	});
2038	}
2039	}
2040	}
2041	if is_section {
2042	group.push(node(0xb8, None, &[])?);
2043	let (chunk, _) = self.list(&group)?;
2044	manifest.push(node(0xb0, Some(Reference::NodeList(chunk)), &payload)?);
2045	let mut overrides = vec![0; 8];
2046	overrides.extend_from_slice(&(!override_crc).to_le_bytes());
2047	manifest.push(node(
2048	0x84,
2049	Some(Reference::Data(Chunk {
2050	offset: u64::MAX,
2051	length: 0,
2052	})),
2053	&overrides,
2054	)?);
2055	} else {
2056	manifest.extend(group);
2057	}
2058	}
2059	if checkpoint {
2060	for (role, id) in &revision.roots {
2061	let mut payload = Vec::new();
2062	if is_section {
2063	id.encode(&mut payload);
2064	} else {
2065	payload.extend_from_slice(&compact(*id, toc_table.as_ref().unwrap())?);
2066	}
2067	payload.extend_from_slice(&role.to_le_bytes());
2068	manifest.push(node(if is_section { 0x5a } else { 0x59 }, None, &payload)?);
2069	}
2070	}
2071	manifest.push(node(0x1c, None, &[])?);
2072	Ok((new_rid, stored))
2073	}
2074
2075	/// Adds a space's manifest nodes to its revision list, creating the space when `new`.
2076	pub(crate) fn close(&mut self, space: ExGuid, new: bool, manifest: &[Vec<u8>]) -> Result<()> {
2077	if new {
2078	let (chunk, tail) = self.list(manifest)?;
2079	let mut payload = Vec::new();
2080	space.encode(&mut payload);
2081	let (chunk, _) = self.list(&[
2082	node(0xc, None, &payload)?,
2083	node(0x10, Some(Reference::NodeList(chunk)), &[])?,
2084	])?;
2085	self.root_nodes
2086	.push(node(8, Some(Reference::NodeList(chunk)), &payload)?);
2087	self.state.spaces.insert(space, tail);
2088	} else {
2089	let mut tail = *self.state.spaces.get(&space).ok_or(Error {
2090	offset: 0,
2091	message: "Object space is absent from the root list",
2092	})?;
2093	self.extend(&mut tail, manifest)?;
2094	self.state.spaces.insert(space, tail);
2095	}
2096	Ok(())
2097	}
2098
2099	/// Embeds payloads as file-data store objects referenced from the root file node list
2100	/// under their identities, as OneNote embeds pictures and attachments.
2101	pub(crate) fn payloads(
2102	&mut self,
2103	payloads: &[([u8; 16], &[u8])],
2104	protection: Option<&dyn Protection>,
2105	) -> Result<()> {
2106	let mut data_nodes = Vec::new();
2107	for (guid, payload) in payloads {
2108	if self.state.file_type != FileType::Section {
2109	return Err(Error {
2110	offset: 0,
2111	message: "Embedded payloads require a section file",
2112	});
2113	}
2114	let mut blob = vec![
2115	0xe7, 0x16, 0xe3, 0xbd, 0x65, 0x26, 0x11, 0x45, 0xa4, 0xc4, 0x8d, 0x4d, 0x0b, 0x7a,
2116	0x9e, 0xac,
2117	];
2118	let sealed = protection
2119	.map(|protection| protection.seal_file(payload))
2120	.transpose()?;
2121	let payload = sealed.as_deref().unwrap_or(*payload);
2122	blob.extend_from_slice(&(payload.len() as u64).to_le_bytes());
2123	blob.extend_from_slice(&[0; 12]);
2124	blob.extend_from_slice(payload);
2125	blob.resize(blob.len().next_multiple_of(8), 0);
2126	blob.extend_from_slice(&[
2127	0x22, 0xa7, 0xfb, 0x71, 0x79, 0x0f, 0x0b, 0x4a, 0xbb, 0x13, 0x89, 0x92, 0x56, 0x42,
2128	0x6b, 0x24,
2129	]);
2130	let chunk = self.append(&blob)?;
2131	data_nodes.push(node(0x94, Some(Reference::Data(chunk)), guid)?);
2132	}
2133	if data_nodes.is_empty() {
2134	return Ok(());
2135	}
2136	// Payload declarations live in the file-data store list the root list references.
2137	match self.state.files {
2138	Some(mut tail) => {
2139	self.extend(&mut tail, &data_nodes)?;
2140	self.state.files = Some(tail);
2141	}
2142	None => {
2143	let (chunk, tail) = self.list(&data_nodes)?;
2144	self.state.files = Some(tail);
2145	self.root_nodes
2146	.push(node(0x90, Some(Reference::NodeList(chunk)), &[])?);
2147	}
2148	}
2149	Ok(())
2150	}
2151
2152	/// The transaction committing what was appended, and the state it leaves; none when
2153	/// nothing was.
2154	pub(crate) fn finish(mut self) -> Result<Option<(crate::Transaction, StoreState)>> {
2155	if !self.root_nodes.is_empty() {
2156	let nodes = std::mem::take(&mut self.root_nodes);
2157	let mut root = self.state.root;
2158	self.extend(&mut root, &nodes)?;
2159	self.state.root = root;
2160	}
2161	if self.counts.is_empty() {
2162	return Ok(None);
2163	}
2164	let file_type = self.state.file_type;
2165	let is_section = file_type == FileType::Section;
2166	let mut header = self.base.header;
2167	let count = u32::from_le_bytes(header[96..100].try_into().unwrap());
2168	let transactions = count.checked_add(1).ok_or(Error {
2169	offset: 96,
2170	message: "Transaction counter is exhausted",
2171	})?;
2172	let changed_bytes = count ^ transactions;
2173	let commit_byte = (31 - changed_bytes.leading_zeros()) / 8;
2174	let ceiling = transactions | ((1_u32 << (commit_byte * 8)) - 1);
2175	let mut entries = Vec::new();
2176	for (id, count) in std::mem::take(&mut self.counts) {
2177	entries.extend_from_slice(&id.to_le_bytes());
2178	entries.extend_from_slice(
2179	&u32::try_from(count)
2180	.map_err(|_| Error {
2181	offset: 0,
2182	message: "File-node count exceeds the format limit",
2183	})?
2184	.to_le_bytes(),
2185	);
2186	}
2187	let (mut log_chunk, mut used) = self.state.log;
2188	let mut checksum = self.state.log_crc;
2189	let mut crc_used = used;
2190	let mut crc_capacity = (log_chunk.length as usize - 12) & !7;
2191	let mut advance_crc = |checksum, entry: &[u8]| {
2192	if crc_used == crc_capacity {
2193	crc_used = 0;
2194	crc_capacity = 1008;
2195	}
2196	crc_used += 8;
2197	transaction_crc(checksum, entry, file_type, crc_used == crc_capacity)
2198	};
2199	for entry in entries.chunks_exact(8) {
2200	checksum = advance_crc(checksum, entry);
2201	}
2202	// Past a counter carry, sentinels up to the ceiling follow the one that commits; the
2203	// next transaction's entries overwrite them, as a reader counting sentinels expects.
2204	let committed = entries.len() + 8;
2205	let mut committed_crc = None;
2206	for _ in transactions..=ceiling {
2207	let sentinel_crc = if is_section { !checksum } else { checksum };
2208	entries.extend_from_slice(&1_u32.to_le_bytes());
2209	entries.extend_from_slice(&sentinel_crc.to_le_bytes());
2210	checksum = advance_crc(checksum, &entries[entries.len() - 8..]);
2211	committed_crc.get_or_insert(checksum);
2212	}
2213	let mut log = self.state.log;
2214	let mut remaining = entries.as_slice();
2215	while !remaining.is_empty() {
2216	let capacity = usize::try_from(log_chunk.length)
2217	.unwrap()
2218	.checked_sub(12)
2219	.map(|size| size & !7)
2220	.filter(|capacity| *capacity >= used)
2221	.ok_or(Error {
2222	offset: usize::try_from(log_chunk.offset).unwrap(),
2223	message: "Transaction fragment has no room for continuation",
2224	})?;
2225	let size = remaining.len().min(capacity - used);
2226	self.write(log_chunk.offset + used as u64, &remaining[..size]);
2227	let written = entries.len() - remaining.len();
2228	if (written + 1..=written + size).contains(&committed) {
2229	log = (log_chunk, used + committed - written);
2230	}
2231	used += size;
2232	remaining = &remaining[size..];
2233	if !remaining.is_empty() {
2234	let mut fragment = vec![0; 1024];
2235	fragment[1008..1016].copy_from_slice(&u64::MAX.to_le_bytes());
2236	let next = self.append(&fragment)?;
2237	let mut reference = next.offset.to_le_bytes().to_vec();
2238	reference.extend_from_slice(&(next.length as u32).to_le_bytes());
2239	self.write(log_chunk.offset + capacity as u64, &reference);
2240	log_chunk = next;
2241	used = 0;
2242	}
2243	}
2244	let length = self.end();
2245	header[96..100].copy_from_slice(&transactions.to_le_bytes());
2246	header[196..204].copy_from_slice(&length.to_le_bytes());
2247	header[212..228].copy_from_slice(&fresh_guid()?);
2248	header[236..252].copy_from_slice(&fresh_guid()?);
2249	let generation = u64::from_le_bytes(header[228..236].try_into().unwrap())
2250	.checked_add(1)
2251	.ok_or(Error {
2252	offset: 228,
2253	message: "File generation counter is exhausted",
2254	})?;
2255	header[228..236].copy_from_slice(&generation.to_le_bytes());
2256	self.state.stamp = crate::Stamp { header, length };
2257	self.state.log = log;
2258	self.state.log_crc = committed_crc.unwrap();
2259	Ok(Some((
2260	crate::Transaction {
2261	base: self.base,
2262	append: self.append,
2263	patches: self.patches,
2264	header,
2265	},
2266	self.state,
2267	)))
2268	}
2269	}
2270
2271	/// The `required` nodes of fragment `sequence` of list `id`, which `bytes` at `at` hold and
2272	/// which ends its list.
2273	fn nodes(
2274	bytes: &[u8],
2275	at: Chunk,
2276	id: u32,
2277	sequence: u32,
2278	required: usize,
2279	) -> Result<Vec<Node<'_>>> {
2280	let fragment = Fragment::parse(bytes, at.offset as usize)?;
2281	if fragment.id != id || fragment.sequence != sequence || !fragment.next.absent() {
2282	return Err(Error {
2283	offset: at.offset as usize,
2284	message: "An appended fragment has the wrong list, sequence or successor",
2285	});
2286	}
2287	let mut nodes = Vec::new();
2288	fragment.nodes(required, &mut nodes, |_| Ok(()))?;
2289	if nodes.len() != required {
2290	return Err(Error {
2291	offset: at.offset as usize,
2292	message: "An appended fragment lacks logged nodes",
2293	});
2294	}
2295	Ok(nodes)
2296	}
2297
2298	/// A revision `Appending::revision` wrote, as `check_transaction` expects to read it back.
2299	pub(crate) struct Written<'r, 'a> {
2300	pub space: ExGuid,
2301	pub rid: ExGuid,
2302	pub previous: Option<ExGuid>,
2303	pub label: (ExGuid, u32),
2304	pub live: &'r LiveRevision<'a>,
2305	pub commit: &'r Commit,
2306	}
2307
2308	/// Reads back what `transaction` appends to the section `before` describes, whose bytes
2309	/// `segments` hold, and checks it stores `revisions`, then each space's `labels` (space,
2310	/// revision, context), and `payloads` as `after` expects:
2311	/// fragments link and decode to the logged counts under the logged checksum; each declared
2312	/// object parses, names identities its group's table holds and objects reachable after its
2313	/// revision, carries its incremental reference count and, if read-only, its MD5; roots stay
2314	/// unless a space is new. Validates nothing the transaction leaves as it was.
2315	#[allow(clippy::too_many_arguments)]
2316	pub(crate) fn check_transaction(
2317	before: &StoreState,
2318	after: &StoreState,
2319	transaction: &crate::Transaction,
2320	segments: &[(u64, &[u8])],
2321	revisions: &[Written<'_, '_>],
2322	labels: &[(ExGuid, ExGuid, ExGuid)],
2323	payloads: &[([u8; 16], &[u8])],
2324	protection: Option<&dyn Protection>,
2325	) -> Result<()> {
2326	let wrong = |message| Error { offset: 0, message };
2327	let encoding: [u8; 2] = if protection.is_some() { [2, 0] } else { [0, 0] };
2328	let base = transaction.base.length;
2329	// A chunk's bytes with this transaction's writes: nothing read here is patched earlier.
2330	let read = |chunk: Chunk| -> Result<Vec<u8>> {
2331	let (start, end) = (chunk.offset, chunk.offset + chunk.length);
2332	let mut bytes = if start >= base {
2333	transaction
2334	.append
2335	.get((start - base) as usize..(end - base) as usize)
2336	.ok_or(wrong("An appended chunk lies outside the transaction"))?
2337	.to_vec()
2338	} else {
2339	let (offset, segment) = segments
2340	.iter()
2341	.rfind(|(offset, _)| *offset <= start)
2342	.ok_or(wrong("A chunk lies outside the store"))?;
2343	segment
2344	.get((start - offset) as usize..(end - offset) as usize)
2345	.ok_or(wrong("A chunk lies outside the store"))?
2346	.to_vec()
2347	};
2348	for (offset, patch) in &transaction.patches {
2349	let (from, to) = (start.max(*offset), end.min(offset + patch.len() as u64));
2350	if from < to {
2351	bytes[(from - start) as usize..(to - start) as usize]
2352	.copy_from_slice(&patch[(from - offset) as usize..(to - offset) as usize]);
2353	}
2354	}
2355	Ok(bytes)
2356	};
2357	let header = &transaction.header;
2358	let count = |header: &[u8; 1024]| u32::from_le_bytes(header[96..100].try_into().unwrap());
2359	if *header != after.stamp.header
2360	|| count(header) != count(&before.stamp.header) + 1
2361	|| u64::from_le_bytes(header[196..204].try_into().unwrap()) != after.stamp.length
2362	|| after.stamp.length != base + transaction.append.len() as u64
2363	{
2364	return Err(wrong("The transaction header does not commit its bytes"));
2365	}
2366
2367	// The log: entries from where it ended, through the sentinel that commits them.
2368	let mut counts = BTreeMap::new();
2369	let (mut chunk, mut used) = before.log;
2370	let mut checksum = before.log_crc;
2371	loop {
2372	let capacity = (chunk.length as usize - 12) & !7;
2373	let bytes = read(chunk)?;
2374	if used == capacity {
2375	let next = u64::from_le_bytes(bytes[capacity..capacity + 8].try_into().unwrap());
2376	let length = u32::from_le_bytes(bytes[capacity + 8..capacity + 12].try_into().unwrap());
2377	(chunk, used) = (
2378	Chunk {
2379	offset: next,
2380	length: u64::from(length),
2381	},
2382	0,
2383	);
2384	continue;
2385	}
2386	let entry = &bytes[used..used + 8];
2387	used += 8;
2388	let id = u32::from_le_bytes(entry[..4].try_into().unwrap());
2389	let value = u32::from_le_bytes(entry[4..].try_into().unwrap());
2390	if id == 1 {
2391	if value != !checksum {
2392	return Err(wrong("The transaction log checksum does not match"));
2393	}
2394	checksum = transaction_crc(checksum, entry, FileType::Section, used == capacity);
2395	break;
2396	}
2397	checksum = transaction_crc(checksum, entry, FileType::Section, used == capacity);
2398	counts.insert(id, value as usize);
2399	}
2400	if (chunk, used) != after.log || checksum != after.log_crc {
2401	return Err(wrong("The transaction log ends elsewhere than its state"));
2402	}
2403
2404	// Nodes a list gained: the fragment `after` ends with, linked from where `before` ended.
2405	let gained = |before: Option<&ListTail>, after: &ListTail| -> Result<Vec<u8>> {
2406	if counts.get(&after.id) != Some(&after.nodes) {
2407	return Err(wrong("A list's nodes disagree with the transaction log"));
2408	}
2409	if let Some(before) = before {
2410	let previous = read(before.last)?;
2411	if Fragment::parse(&previous, before.last.offset as usize)?.next != after.last
2412	|| after.fragments != before.fragments + 1
2413	|| after.id != before.id
2414	{
2415	return Err(wrong("An appended fragment is not linked to its list"));
2416	}
2417	}
2418	read(after.last)
2419	};
2420	// Each space's list gains one fragment: its revisions in order, then its labels.
2421	let mut spaces: Vec<ExGuid> = Vec::new();
2422	for space in revisions
2423	.iter()
2424	.map(|written| written.space)
2425	.chain(labels.iter().map(|(space, ..)| *space))
2426	{
2427	if !spaces.contains(&space) {
2428	spaces.push(space);
2429	}
2430	}
2431	for space in spaces {
2432	let old = before.spaces.get(&space);
2433	let new = after
2434	.spaces
2435	.get(&space)
2436	.ok_or(wrong("A sealed space has no list"))?;
2437	let bytes = gained(old, new)?;
2438	let manifest = nodes(
2439	&bytes,
2440	new.last,
2441	new.id,
2442	old.map_or(0, |old| old.fragments),
2443	new.nodes - old.map_or(0, |old| old.nodes),
2444	)?;
2445	let mut manifest = manifest.iter();
2446	let mut next = || {
2447	manifest
2448	.next()
2449	.ok_or(wrong("A revision manifest is truncated"))
2450	};
2451	let mut fresh = old.is_none();
2452	for written in revisions.iter().filter(|written| written.space == space) {
2453	let Written {
2454	rid,
2455	live,
2456	commit,
2457	label,
2458	..
2459	} = *written;
2460	let mut node = next()?;
2461	if fresh {
2462	let mut c = Cursor {
2463	bytes: node.payload,
2464	offset: node.offset,
2465	};
2466	if node.id != 0x14 || c.exguid()? != space {
2467	return Err(wrong("A new space's revision list names another space"));
2468	}
2469	node = next()?;
2470	fresh = false;
2471	}
2472	let mut c = Cursor {
2473	bytes: node.payload,
2474	offset: node.offset,
2475	};
2476	let dependency = if commit.checkpoint {
2477	ExGuid::default()
2478	} else {
2479	written
2480	.previous
2481	.ok_or(wrong("A dependent revision follows none"))?
2482	};
2483	let contextual = label.0 != ExGuid::default();
2484	if node.id != if contextual { 0x1f } else { 0x1e }
2485	|| c.exguid()? != rid
2486	|| c.exguid()? != dependency
2487	|| c.read::<4>()? != label.1.to_le_bytes()
2488	|| c.read::<2>()? != encoding
2489	|| (contextual && c.exguid()? != label.0)
2490	{
2491	return Err(wrong(
2492	"A revision starts with the wrong identity, dependency or label",
2493	));
2494	}
2495	if let Some(protection) = protection {
2496	let node = next()?;
2497	if node.id != 0x7c || node.reference != Some(Reference::Data(protection.metadata()))
2498	{
2499	return Err(wrong("A protected revision does not name its key"));
2500	}
2501	}
2502	let mut declared = BTreeSet::new();
2503	let mut roots = BTreeMap::new();
2504	loop {
2505	let node = next()?;
2506	match node.id {
2507	0xb0 => {
2508	let Some(Reference::NodeList(at)) = node.reference else {
2509	return Err(wrong("An object group lacks its list"));
2510	};
2511	let bytes = read(at)?;
2512	let id = Fragment::parse(&bytes, at.offset as usize)?.id;
2513	let required = *counts
2514	.get(&id)
2515	.ok_or(wrong("An object group is not logged"))?;
2516	let group = nodes(&bytes, at, id, 0, required)?;
2517	let mut table = BTreeMap::new();
2518	let mut override_crc = u32::MAX;
2519	for item in &group {
2520	let mut c = Cursor {
2521	bytes: item.payload,
2522	offset: item.offset,
2523	};
2524	match item.id {
2525	0xb4 | 0x22 | 0x28 | 0xb8 => {}
2526	0x24 => {
2527	table.insert(u32::from_le_bytes(c.read()?), c.read::<16>()?);
2528	}
2529	0xa5 | 0xc5 | 0x73 => {
2530	let id = c.compact(&table)?;
2531	let object =
2532	live.revision.objects.get(&id).ok_or(wrong(
2533	"A revision declares an unknown object",
2534	))?;
2535	let jcid = u32::from_le_bytes(c.read()?);
2536	let flags = if item.id == 0x73 {
2537	None
2538	} else {
2539	Some(c.read::<1>()?[0])
2540	};
2541	let count = u32::from_le_bytes(c.read()?);
2542	if !declared.insert(id)
2543	|| jcid != object.jcid
2544	|| count != object.reference_count
2545	{
2546	return Err(wrong(
2547	"A declaration disagrees with its object or its count",
2548	));
2549	}
2550	override_crc =
2551	crc(override_crc, &count.to_le_bytes(), FileType::Section);
2552	if item.id == 0x73 {
2553	continue;
2554	}
2555	let Some(Reference::Data(at)) = item.reference else {
2556	return Err(wrong("An object declaration lacks its data"));
2557	};
2558	let data = read(at)?;
2559	let clear = match protection {
2560	Some(protection) => protection.open_property(&data)?,
2561	None => zeroize::Zeroizing::new(data.clone()),
2562	};
2563	let stored = crate::Object {
2564	jcid,
2565	reference_count: count,
2566	data: ObjectData::Properties(&clear),
2567	global_ids: Arc::new(table.clone()),
2568	};
2569	let references = stored.references()?;
2570	let expected = u8::from(!references.objects.is_empty())
2571	| (u8::from(
2572	!references.object_spaces.is_empty()
2573	|| !references.contexts.is_empty(),
2574	) << 1);
2575	let hash = match protection {
2576	Some(_) => crate::protected::digest(&clear),
2577	None => md5::compute(&data).0,
2578	};
2579	if object.data != ObjectData::Properties(&clear)
2580	|| flags != Some(expected)
2581	|| (item.id == 0xc5) != (jcid & 0x100000 != 0)
2582	|| (item.id == 0xc5 && c.read::<16>()? != hash)
2583	{
2584	return Err(wrong(
2585	"An object's stored bytes differ from its revision",
2586	));
2587	}
2588	if live.is_reachable(id)
2589	&& !references
2590	.objects
2591	.iter()
2592	.all(|target| live.is_reachable(*target))
2593	{
2594	return Err(wrong(
2595	"An object references one its revision cannot reach",
2596	));
2597	}
2598	}
2599	_ => return Err(wrong("Unexpected node in an object group")),
2600	}
2601	}
2602	let node = next()?;
2603	let mut c = Cursor {
2604	bytes: node.payload,
2605	offset: node.offset,
2606	};
2607	if node.id != 0x84
2608	|| c.read::<8>()? != [0; 8]
2609	|| u32::from_le_bytes(c.read()?) != !override_crc
2610	{
2611	return Err(wrong("An object group's count overrides do not match"));
2612	}
2613	}
2614	0x5a => {
2615	let mut c = Cursor {
2616	bytes: node.payload,
2617	offset: node.offset,
2618	};
2619	let id = c.exguid()?;
2620	roots.insert(u32::from_le_bytes(c.read()?), id);
2621	}
2622	0x1c => break,
2623	_ => return Err(wrong("Unexpected node in a revision manifest")),
2624	}
2625	}
2626	let expected: BTreeSet<ExGuid> = if commit.checkpoint {
2627	live.revision.objects.keys().copied().collect()
2628	} else {
2629	commit.changed.clone()
2630	};
2631	if declared != expected
2632	|| (commit.checkpoint && roots != live.revision.roots)
2633	|| (!commit.checkpoint && !roots.is_empty())
2634	{
2635	return Err(wrong(
2636	"A revision declares other objects or roots than it changed",
2637	));
2638	}
2639	}
2640	for (_, rid, context) in labels.iter().filter(|(labelled, ..)| *labelled == space) {
2641	let node = next()?;
2642	if node.id != 0x5d || node.payload != label_payload(*rid, *context) {
2643	return Err(wrong("A revision label names another revision or context"));
2644	}
2645	}
2646	if next().is_ok() {
2647	return Err(wrong(
2648	"A revision list gains nodes no revision or label declares",
2649	));
2650	}
2651	}
2652
2653	if after.root.nodes != before.root.nodes {
2654	let bytes = gained(Some(&before.root), &after.root)?;
2655	let added = nodes(
2656	&bytes,
2657	after.root.last,
2658	after.root.id,
2659	before.root.fragments,
2660	after.root.nodes - before.root.nodes,
2661	)?;
2662	let created = revisions
2663	.iter()
2664	.map(|written| written.space)
2665	.filter(|space| !before.spaces.contains_key(space))
2666	.collect::<BTreeSet<_>>()
2667	.len();
2668	let spaces = added.iter().filter(|node| node.id == 8).count();
2669	if spaces != created || added.iter().any(|node| !matches!(node.id, 8 | 0x90)) {
2670	return Err(wrong(
2671	"The root list gains other nodes than new spaces declare",
2672	));
2673	}
2674	}
2675	if !payloads.is_empty() {
2676	let files = after
2677	.files
2678	.as_ref()
2679	.ok_or(wrong("Embedded payloads have no store"))?;
2680	let bytes = gained(before.files.as_ref(), files)?;
2681	let declared = nodes(
2682	&bytes,
2683	files.last,
2684	files.id,
2685	before.files.map_or(0, |files| files.fragments),
2686	payloads.len(),
2687	)?;
2688	for ((guid, payload), node) in payloads.iter().zip(&declared) {
2689	let Some(Reference::Data(at)) = node.reference else {
2690	return Err(wrong("A payload declaration lacks its data"));
2691	};
2692	let data = read(at)?;
2693	let blob = crate::files::payload(&data, at.offset as usize)?;
2694	let blob = match protection {
2695	Some(protection) => protection.open_file(blob)?,
2696	None => zeroize::Zeroizing::new(blob.to_vec()),
2697	};
2698	if node.id != 0x94 || node.payload != guid || blob.as_slice() != *payload {
2699	return Err(wrong("An embedded payload differs from its declaration"));
2700	}
2701	}
2702	}
2703	Ok(())
2704	}