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	.as_chunks::<4>()
144	.0
145	.iter()
146	.map(|id| u32::from_le_bytes(*id) >> 8),
147	);
148	}
149	}
150	Ok(entries)
151	}
152
153	fn field_length(property: &crate::Property<'_>, set_lengths: &[usize]) -> usize {
154	match &property.value {
155	Value::NoData => 0,
156	Value::Bytes(bytes) => bytes.len() + usize::from(property.id >> 26 & 31 == 7) * 4,
157	Value::References { .. } => usize::from(property.id >> 26 & 1 != 0) * 4,
158	Value::Sets(children) => {
159	let prefix = if property.id >> 26 & 31 == 16 {
160	if children.is_empty() { 4 } else { 8 }
161	} else {
162	0
163	};
164	prefix + children.clone().map(|i| set_lengths[i]).sum::<usize>()
165	}
166	}
167	}
168
169	fn property_set_lengths(properties: &PropertySets<'_>) -> Vec<usize> {
170	let mut lengths = vec![0; properties.sets.len()];
171	for (i, set) in properties.sets.iter().enumerate().rev() {
172	lengths[i] =
173	2 + set.len() * 4 + set.iter().map(|p| field_length(p, &lengths)).sum::<usize>();
174	}
175	lengths
176	}
177
178	fn patch_properties(
179	blob: &[u8],
180	updates: &[(u32, &[u8])],
181	inserts: &[(u32, &[u8])],
182	nested_references: &[u8],
183	) -> Result<Vec<u8>> {
184	let properties = PropertySets::parse(blob)?;
185	let root = &properties.sets[0];
186	let ids = properties.root_ids.as_ptr().addr() - blob.as_ptr().addr();
187	let ids_end = ids + properties.root_ids.len();
188	let body_end = blob.len() - properties.padding.len();
189	let set_lengths = property_set_lengths(&properties);
190	let mut offsets = Vec::with_capacity(root.len());
191	let mut offset = ids_end;
192	for property in root {
193	offsets.push(offset);
194	offset += field_length(property, &set_lengths);
195	}
196	let mut patches = Vec::new();
197	let mut added_ids = Vec::new();
198	let mut added_fields = Vec::new();
199	let mut added_references = Vec::new();
200	let object_header = u32::from_le_bytes(blob[..4].try_into().unwrap());
201	let mut object_count = i64::from(object_header & 0xffffff);
202	let mut seen = BTreeSet::new();
203	for (i, &(property, value)) in updates.iter().chain(inserts).enumerate() {
204	if !seen.insert(property & 0x7fffffff) {
205	return Err(Error {
206	offset: 0,
207	message: "Duplicate property update",
208	});
209	}
210	let kind = (property >> 26) & 31;
211	let valid = match kind {
212	2 => value.is_empty(),
213	3..=6 => value.len() == 1 << (kind - 3),
214	7 => value.len() < 0x40000000,
215	8 => value.len() == 4,
216	9 => value.len().is_multiple_of(4) && value.len() / 4 <= 0xffffff,
217	// An encoded property-set array is inserted whole; its references follow.
218	16 => i >= updates.len() && value.len() >= 4,
219	_ => {
220	return Err(Error {
221	offset: 0,
222	message: "Property type cannot be patched",
223	});
224	}
225	};
226	if !valid || (kind != 2 && property & 0x80000000 != 0) {
227	return Err(Error {
228	offset: 0,
229	message: "Replacement has an invalid property value",
230	});
231	}
232	let matches: Vec<_> = root
233	.iter()
234	.enumerate()
235	.filter(|(_, p)| p.id & 0x7fffffff == property & 0x7fffffff)
236	.collect();
237	let adding = i >= updates.len();
238	if matches.len() != usize::from(!adding) {
239	return Err(Error {
240	offset: 0,
241	message: "Property is missing or duplicated",
242	});
243	}
244	let mut encoded = Vec::new();
245	match kind {
246	7 => encoded.extend_from_slice(&(value.len() as u32).to_le_bytes()),
247	9 => encoded.extend_from_slice(&(value.len() as u32 / 4).to_le_bytes()),
248	_ => {}
249	}
250	if (3..=7).contains(&kind) || kind == 16 {
251	encoded.extend_from_slice(value);
252	}
253	if adding {
254	added_ids.extend_from_slice(&property.to_le_bytes());
255	added_fields.extend_from_slice(&encoded);
256	if (8..=9).contains(&kind) {
257	object_count += (value.len() / 4) as i64;
258	added_references.extend_from_slice(value);
259	}
260	} else {
261	let (index, previous) = matches[0];
262	if kind == 2 && previous.id != property {
263	patches.push((
264	ids + index * 4,
265	ids + index * 4 + 4,
266	index,
267	property.to_le_bytes().to_vec(),
268	));
269	}
270	let start = offsets[index];
271	let end = start + field_length(previous, &set_lengths);
272	if blob[start..end] != encoded {
273	patches.push((start, end, index, encoded));
274	}
275	if let Value::References { compact_ids, .. } = previous.value {
276	object_count += (value.len() / 4) as i64 - (compact_ids.len() / 4) as i64;
277	if compact_ids != value {
278	let start = compact_ids.as_ptr().addr() - blob.as_ptr().addr();
279	patches.push((start, start + compact_ids.len(), index, value.to_vec()));
280	}
281	}
282	}
283	}
284	object_count += (nested_references.len() / 4) as i64;
285	if !(0..=0xffffff).contains(&object_count) {
286	return Err(Error {
287	offset: 0,
288	message: "Object reference stream exceeds the format limit",
289	});
290	}
291	let header = (object_header & 0xff000000) | object_count as u32;
292	if header != object_header {
293	patches.push((0, 4, 0, header.to_le_bytes().to_vec()));
294	}
295	added_references.extend_from_slice(nested_references);
296	if !added_references.is_empty() {
297	let end = 4 + (object_header as usize & 0xffffff) * 4;
298	patches.push((end, end, usize::MAX, added_references));
299	}
300	if !inserts.is_empty() {
301	let count = u16::try_from(root.len() + inserts.len()).map_err(|_| Error {
302	offset: ids - 2,
303	message: "Root property count exceeds the format limit",
304	})?;
305	patches.push((ids - 2, ids, 0, count.to_le_bytes().to_vec()));
306	patches.push((ids_end, ids_end, usize::MAX - 1, added_ids));
307	patches.push((body_end, body_end, usize::MAX, added_fields));
308	}
309	if patches.is_empty() {
310	return Ok(blob.to_vec());
311	}
312	patches.sort_by_key(|(start, end, order, _)| (*start, *end, *order));
313	let mut changed = Vec::new();
314	let mut cursor = 0;
315	for (start, end, _, value) in patches {
316	if start < cursor {
317	return Err(Error {
318	offset: start,
319	message: "Property patches overlap",
320	});
321	}
322	changed.extend_from_slice(&blob[cursor..start]);
323	changed.extend_from_slice(&value);
324	cursor = end;
325	}
326	changed.extend_from_slice(&blob[cursor..body_end]);
327	changed.resize(changed.len().next_multiple_of(8), 0);
328	PropertySets::parse(&changed)?;
329	Ok(changed)
330	}
331
332	pub(crate) struct ObjectEdit<'a> {
333	pub object: ExGuid,
334	pub updates: &'a [(u32, &'a [u8])],
335	pub inserts: &'a [(u32, &'a [u8])],
336	}
337
338	/// Objects of `revision` with `edits` applied.
339	pub(crate) fn patched(
340	revision: &crate::ResolvedRevision<'_>,
341	edits: &[ObjectEdit<'_>],
342	) -> Result<BTreeMap<ExGuid, PropertyObject>> {
343	let mut changed = BTreeMap::new();
344	for edit in edits {
345	if changed.contains_key(&edit.object) {
346	return Err(Error {
347	offset: 0,
348	message: "Duplicate object edit",
349	});
350	}
351	let object = revision.objects.get(&edit.object).ok_or(Error {
352	offset: 0,
353	message: "Object is absent from the active revision",
354	})?;
355	let ObjectData::Properties(blob) = object.data else {
356	return Err(Error {
357	offset: 0,
358	message: "Object does not contain editable properties",
359	});
360	};
361	changed.insert(
362	edit.object,
363	PropertyObject {
364	jcid: object.jcid,
365	bytes: patch_properties(blob, edit.updates, edit.inserts, &[])?,
366	global_ids: Arc::clone(&object.global_ids),
367	},
368	);
369	}
370	Ok(changed)
371	}
372
373	/// Whether `after` stores as `before` does: the same type and bytes, naming the same
374	/// identities. Stored tables keep only the entries an object names, so those decide.
375	pub(crate) fn unchanged(before: &crate::Object<'_>, after: &crate::Object<'_>) -> Result<bool> {
376	if before.jcid != after.jcid || before.data != after.data {
377	return Ok(false);
378	}
379	let entries = match after.data {
380	ObjectData::Properties(bytes) => table_entries(bytes)?,
381	_ => Vec::new(),
382	};
383	Ok(entries
384	.iter()
385	.all(|entry| before.global_ids.get(entry) == after.global_ids.get(entry)))
386	}
387
388	/// `object` as a replacement a revision stores under `id`.
389	pub(crate) fn replacement(id: ExGuid, object: &crate::Object<'_>) -> Result<PropertyObject> {
390	let mut replacement = match object.data {
391	ObjectData::Properties(_) => PropertyObject::from_object(object)?,
392	ObjectData::File {
393	reference,
394	extension,
395	} => {
396	let text = |bytes: &[u8]| {
397	String::from_utf16(
398	&bytes
399	.as_chunks::<2>()
400	.0
401	.iter()
402	.map(|pair| u16::from_le_bytes([pair[0], pair[1]]))
403	.collect::<Vec<_>>(),
404	)
405	.map_err(|_| Error {
406	offset: 0,
407	message: "Invalid UTF-16 file-data declaration",
408	})
409	};
410	let mut replacement = PropertyObject::file(id, &text(reference)?, &text(extension)?)?;
411	replacement.jcid = object.jcid;
412	replacement
413	}
414	ObjectData::Encrypted(_) => {
415	return Err(Error {
416	offset: 0,
417	message: "Page edits only produce property objects",
418	});
419	}
420	};
421	replacement.reference(id)?;
422	Ok(replacement)
423	}
424
425	/// The object type OneNote gives embedded picture payload declarations; embedded files
426	/// use `EMBEDDED_FILE_JCID` with the same declaration shape, and a printout's XPS package
427	/// `PRINTOUT_FILE_JCID` (`corpus/printout`).
428	pub(crate) const FILE_DATA_JCID: u32 = 0x80039;
429	pub(crate) const EMBEDDED_FILE_JCID: u32 = 0x80036;
430	pub(crate) const PRINTOUT_FILE_JCID: u32 = 0x8003a;
431
432	/// The reference and extension of a file-data declaration built by `PropertyObject::file`.
433	fn file_declaration(bytes: &[u8]) -> Result<(&[u8], &[u8])> {
434	let malformed = || Error {
435	offset: 0,
436	message: "Malformed file-data declaration",
437	};
438	let mut rest = bytes;
439	let mut parts = Vec::new();
440	for _ in 0..2 {
441	let length = usize::try_from(u32::from_le_bytes(
442	rest.get(..4).ok_or_else(malformed)?.try_into().unwrap(),
443	))
444	.map_err(|_| malformed())?;
445	let bytes = rest.get(4..4 + length).ok_or_else(malformed)?;
446	parts.push(bytes);
447	rest = &rest[4 + length..];
448	}
449	if !rest.is_empty() {
450	return Err(malformed());
451	}
452	Ok((parts[0], parts[1]))
453	}
454
455	/// An object of type `jcid` stored as `bytes`, as a revision declares it.
456	pub(crate) fn declared(
457	jcid: u32,
458	bytes: &[u8],
459	global_ids: Arc<BTreeMap<u32, [u8; 16]>>,
460	) -> Result<crate::Object<'_>> {
461	let data = if is_file_declaration(jcid) {
462	let (reference, extension) = file_declaration(bytes)?;
463	ObjectData::File {
464	reference,
465	extension,
466	}
467	} else {
468	ObjectData::Properties(bytes)
469	};
470	Ok(crate::Object {
471	jcid,
472	reference_count: 0,
473	data,
474	global_ids,
475	})
476	}
477
478	fn is_file_declaration(jcid: u32) -> bool {
479	matches!(
480	jcid,
481	FILE_DATA_JCID | EMBEDDED_FILE_JCID | PRINTOUT_FILE_JCID
482	)
483	}
484
485	#[derive(Clone)]
486	pub(crate) struct PropertyObject {
487	pub jcid: u32,
488	pub bytes: Vec<u8>,
489	pub global_ids: Arc<BTreeMap<u32, [u8; 16]>>,
490	}
491
492	pub(crate) enum RevisionEdit {
493	Update(BTreeMap<ExGuid, PropertyObject>),
494	#[cfg(test)]
495	Create {
496	roots: BTreeMap<u32, ExGuid>,
497	objects: BTreeMap<ExGuid, PropertyObject>,
498	},
499	}
500
501	impl PropertyObject {
502	/// A file-data object declaring an embedded payload by its store identity, or an
503	/// external payload by name; `extension` includes its leading dot.
504	pub fn file(id: ExGuid, reference: &str, extension: &str) -> Result<Self> {
505	if reference.is_empty() || reference.contains('\0') || extension.contains('\0') {
506	return Err(Error {
507	offset: 0,
508	message: "File-data references and extensions are nonempty and contain no NUL",
509	});
510	}
511	let mut bytes = Vec::new();
512	for text in [reference, extension] {
513	let encoded: Vec<u8> = text.encode_utf16().flat_map(u16::to_le_bytes).collect();
514	bytes.extend_from_slice(&u32::try_from(encoded.len()).unwrap().to_le_bytes());
515	bytes.extend_from_slice(&encoded);
516	}
517	Ok(Self {
518	jcid: FILE_DATA_JCID,
519	bytes,
520	global_ids: Arc::new(BTreeMap::from([(0, id.guid)])),
521	})
522	}
523
524	pub fn from_object(object: &crate::Object<'_>) -> Result<Self> {
525	let ObjectData::Properties(bytes) = object.data else {
526	return Err(Error {
527	offset: 0,
528	message: "Object does not contain editable properties",
529	});
530	};
531	Ok(Self {
532	jcid: object.jcid,
533	bytes: bytes.to_vec(),
534	global_ids: Arc::clone(&object.global_ids),
535	})
536	}
537
538	pub fn set(&mut self, values: &[(u32, &[u8])]) -> Result<()> {
539	let properties = PropertySets::parse(&self.bytes)?;
540	let (updates, inserts): (Vec<_>, Vec<_>) = values.iter().copied().partition(|(id, _)| {
541	properties.sets[0]
542	.iter()
543	.any(|p| p.id & 0x7fffffff == id & 0x7fffffff)
544	});
545	self.bytes = patch_properties(&self.bytes, &updates, &inserts, &[])?;
546	Ok(())
547	}
548
549	/// Replaces a property-set array such as note tags: each set lists scalar values
550	/// inline, while an object reference (a kind-8 identity) is supplied as the compact
551	/// identity `reference` produced and joins the object's reference stream in order.
552	pub fn set_sets(&mut self, id: u32, element: u32, sets: &[Vec<(u32, Vec<u8>)>]) -> Result<()> {
553	if (id >> 26) & 31 != 16 || (element >> 26) & 31 != 17 {
554	return Err(Error {
555	offset: 0,
556	message: "Property-set arrays need array and element identifiers",
557	});
558	}
559	self.remove(&[id])?;
560	if sets.is_empty() {
561	return Ok(());
562	}
563	let mut encoded = (sets.len() as u32).to_le_bytes().to_vec();
564	encoded.extend_from_slice(&element.to_le_bytes());
565	let mut references = Vec::new();
566	for set in sets {
567	encoded.extend_from_slice(&u16::try_from(set.len()).unwrap().to_le_bytes());
568	for (field, _) in set {
569	encoded.extend_from_slice(&field.to_le_bytes());
570	}
571	for (field, value) in set {
572	match (field >> 26) & 31 {
573	3..=6 => {
574	assert_eq!(value.len(), 1 << (((field >> 26) & 31) - 3));
575	encoded.extend_from_slice(value);
576	}
577	7 => {
578	encoded.extend_from_slice(&(value.len() as u32).to_le_bytes());
579	encoded.extend_from_slice(value);
580	}
581	8 => {
582	assert_eq!(value.len(), 4);
583	references.extend_from_slice(value);
584	}
585	_ => {
586	return Err(Error {
587	offset: 0,
588	message: "Property-set arrays hold scalars and single references",
589	});
590	}
591	}
592	}
593	}
594	self.bytes = patch_properties(&self.bytes, &[], &[(id, &encoded)], &references)?;
595	Ok(())
596	}
597
598	pub fn remove(&mut self, ids: &[u32]) -> Result<()> {
599	let properties = PropertySets::parse(&self.bytes)?;
600	let removed = |id: u32| {
601	ids.iter()
602	.any(|wanted| id & 0x7fffffff == wanted & 0x7fffffff)
603	};
604	if !properties.sets[0].iter().any(|p| removed(p.id)) {
605	return Ok(());
606	}
607	let lengths = property_set_lengths(&properties);
608	let mut offset = properties.root_ids.as_ptr().addr() - self.bytes.as_ptr().addr()
609	+ properties.root_ids.len();
610	let mut retained_ids = Vec::new();
611	let mut fields = Vec::new();
612	let mut references: [Vec<u8>; 3] = std::array::from_fn(|_| Vec::new());
613	for property in &properties.sets[0] {
614	let end = offset + field_length(property, &lengths);
615	if !removed(property.id) {
616	retained_ids.extend_from_slice(&property.id.to_le_bytes());
617	fields.extend_from_slice(&self.bytes[offset..end]);
618	let mut pending = vec![property];
619	while let Some(field) = pending.pop() {
620	match &field.value {
621	Value::References {
622	stream,
623	compact_ids,
624	} => {
625	let index = match stream {
626	crate::IdStream::Objects => 0,
627	crate::IdStream::ObjectSpaces => 1,
628	crate::IdStream::Contexts => 2,
629	};
630	references[index].extend_from_slice(compact_ids);
631	}
632	Value::Sets(children) => {
633	for child in children.clone().rev() {
634	pending.extend(properties.sets[child].iter().rev());
635	}
636	}
637	_ => {}
638	}
639	}
640	}
641	offset = end;
642	}
643	let mut cursor = crate::bytes::Cursor {
644	bytes: &self.bytes,
645	offset: 0,
646	};
647	let streams = crate::properties::reference_streams(&mut cursor)?;
648	let mut bytes = Vec::new();
649	for (stream, retained) in streams.iter().zip(&references) {
650	if stream.offset == 0 {
651	continue;
652	}
653	let header = u32::from_le_bytes(
654	self.bytes[stream.offset - 4..stream.offset]
655	.try_into()
656	.unwrap(),
657	);
658	let count = u32::try_from(retained.len() / 4).unwrap();
659	bytes.extend_from_slice(&((header & 0xff000000) | count).to_le_bytes());
660	bytes.extend_from_slice(retained);
661	}
662	bytes.extend_from_slice(&u16::try_from(retained_ids.len() / 4).unwrap().to_le_bytes());
663	bytes.extend_from_slice(&retained_ids);
664	bytes.extend_from_slice(&fields);
665	bytes.resize(bytes.len().next_multiple_of(8), 0);
666	PropertySets::parse(&bytes)?;
667	self.bytes = bytes;
668	Ok(())
669	}
670
671	pub fn reference(&mut self, id: ExGuid) -> Result<[u8; 4]> {
672	if !self.global_ids.values().any(|guid| *guid == id.guid) {
673	let mut index = 0;
674	for key in self.global_ids.keys() {
675	if *key != index {
676	break;
677	}
678	index += 1;
679	}
680	if index >= 0xffffff || id.guid == [0; 16] {
681	return Err(Error {
682	offset: 0,
683	message: "Object identity cannot be added to the global ID table",
684	});
685	}
686	Arc::make_mut(&mut self.global_ids).insert(index, id.guid);
687	}
688	compact(id, &self.global_ids)
689	}
690
691	pub fn copy_property(&mut self, source: &Self, id: u32) -> Result<()> {
692	let properties = PropertySets::parse(&source.bytes)?;
693	let mut target = Self {
694	jcid: self.jcid,
695	bytes: self.bytes.clone(),
696	global_ids: Arc::clone(&self.global_ids),
697	};
698	target.remove(&[id])?;
699	let lengths = property_set_lengths(&properties);
700	let mut offset = properties.root_ids.as_ptr().addr() - source.bytes.as_ptr().addr()
701	+ properties.root_ids.len();
702	let mut selected = None;
703	for property in &properties.sets[0] {
704	let end = offset + field_length(property, &lengths);
705	if property.id & 0x7fffffff == id & 0x7fffffff {
706	selected = Some((property, &source.bytes[offset..end]));
707	break;
708	}
709	offset = end;
710	}
711	if let Some((property, field)) = selected {
712	let mut added: [Vec<u8>; 3] = std::array::from_fn(|_| Vec::new());
713	let mut pending = vec![property];
714	while let Some(property) = pending.pop() {
715	match &property.value {
716	Value::References {
717	stream,
718	compact_ids,
719	} => {
720	let index = match stream {
721	crate::IdStream::Objects => 0,
722	crate::IdStream::ObjectSpaces => 1,
723	crate::IdStream::Contexts => 2,
724	};
725	let mut cursor = crate::bytes::Cursor {
726	bytes: compact_ids,
727	offset: 0,
728	};
729	while !cursor.bytes.is_empty() {
730	let id = cursor.compact(&source.global_ids)?;
731	added[index].extend_from_slice(&target.reference(id)?);
732	}
733	}
734	Value::Sets(children) => {
735	for child in children.clone().rev() {
736	pending.extend(properties.sets[child].iter().rev());
737	}
738	}
739	_ => {}
740	}
741	}
742	let old = PropertySets::parse(&target.bytes)?;
743	let count = u16::try_from(old.sets[0].len() + 1).map_err(|_| Error {
744	offset: 0,
745	message: "Root property count exceeds the format limit",
746	})?;
747	let streams = crate::properties::reference_streams(&mut crate::bytes::Cursor {
748	bytes: &target.bytes,
749	offset: 0,
750	})?;
751	let stream_count = (0..3)
752	.rev()
753	.find(|i| streams[*i].offset != 0 || !added[*i].is_empty())
754	.unwrap()
755	+ 1;
756	let mut bytes = Vec::new();
757	for i in 0..stream_count {
758	let stream = &streams[i];
759	let count = u32::try_from((stream.bytes.len() + added[i].len()) / 4)
760	.ok()
761	.filter(|n| *n <= 0xffffff)
762	.ok_or(Error {
763	offset: 0,
764	message: "Reference stream exceeds the format limit",
765	})?;
766	let reserved = if stream.offset == 0 {
767	0
768	} else {
769	u32::from_le_bytes(
770	target.bytes[stream.offset - 4..stream.offset]
771	.try_into()
772	.unwrap(),
773	) & 0x3f000000
774	};
775	let flags = match (i, stream_count) {
776	(0, 1) => 0x80000000,
777	(0 | 1, 3) => 0x40000000,
778	_ => 0,
779	};
780	bytes.extend_from_slice(&(count | reserved | flags).to_le_bytes());
781	bytes.extend_from_slice(stream.bytes);
782	bytes.extend_from_slice(&added[i]);
783	}
784	bytes.extend_from_slice(&count.to_le_bytes());
785	bytes.extend_from_slice(old.root_ids);
786	bytes.extend_from_slice(&property.id.to_le_bytes());
787	let start =
788	old.root_ids.as_ptr().addr() - target.bytes.as_ptr().addr() + old.root_ids.len();
789	bytes.extend_from_slice(&target.bytes[start..target.bytes.len() - old.padding.len()]);
790	bytes.extend_from_slice(field);
791	bytes.resize(bytes.len().next_multiple_of(8), 0);
792	PropertySets::parse(&bytes)?;
793	target.bytes = bytes;
794	}
795	*self = target;
796	Ok(())
797	}
798	}
799
800	/// A password-protected section's key, under which a writer stores what it appends.
801	pub(crate) trait Protection {
802	/// The stored bytes an object's clear bytes were decoded from.
803	fn stored(&self, clear: &[u8]) -> Option<&[u8]>;
804	fn seal_property(&self, clear: &[u8]) -> Result<Vec<u8>>;
805	fn seal_file(&self, clear: &[u8]) -> Result<Vec<u8>>;
806	fn open_property(&self, stored: &[u8]) -> Result<zeroize::Zeroizing<Vec<u8>>>;
807	fn open_file(&self, stored: &[u8]) -> Result<zeroize::Zeroizing<Vec<u8>>>;
808	/// The encryption data's chunk, which every revision names.
809	fn metadata(&self) -> Chunk;
810	}
811
812	/// The global-ID entries a group of objects declared together uses: each object's own
813	/// and those its properties reference. A section's group stores only these.
814	fn used_entries<'o>(
815	table: &BTreeMap<u32, [u8; 16]>,
816	objects: impl IntoIterator<Item = (ExGuid, &'o crate::Object<'o>)>,
817	) -> Result<Vec<u32>> {
818	let mut used = Vec::new();
819	for (id, object) in objects {
820	used.push(u32::from_le_bytes(compact(id, table)?) >> 8);
821	if let ObjectData::Properties(bytes) = object.data {
822	used.extend(table_entries(bytes)?);
823	}
824	}
825	used.sort_unstable();
826	used.dedup();
827	Ok(used)
828	}
829
830	/// A space's revision as appending a revision and reading it back leaves it.
831	#[derive(Clone)]
832	pub(crate) struct LiveRevision<'a> {
833	pub revision: crate::ResolvedRevision<'a>,
834	/// Incoming references of each object reachable from the roots; a root counts once.
835	incoming: BTreeMap<ExGuid, u32>,
836	/// Reachable read-only property objects by type and content, which identical new
837	/// objects alias.
838	readonly: BTreeMap<u32, BTreeMap<&'a [u8], BTreeSet<ExGuid>>>,
839	/// Revisions in the dependency chain, counted to 512; zero before the first.
840	pub depth: usize,
841	}
842
843	impl<'a> LiveRevision<'a> {
844	pub(crate) fn new(revision: crate::ResolvedRevision<'a>, depth: usize) -> Result<Self> {
845	let incoming = if depth == 0 {
846	BTreeMap::new()
847	} else {
848	revision.checked_counts()?
849	};
850	let mut readonly = BTreeMap::new();
851	for id in incoming.keys() {
852	index(&mut readonly, *id, &revision.objects[id], true);
853	}
854	Ok(Self {
855	revision,
856	incoming,
857	readonly,
858	depth,
859	})
860	}
861
862	pub(crate) fn is_reachable(&self, id: ExGuid) -> bool {
863	self.incoming.contains_key(&id)
864	}
865
866	/// Validates replacements and drops what the revision would not store: new read-only
867	/// objects identical to reachable or earlier ones, whose references move to those, and
868	/// reachable objects that stay as they are.
869	pub(crate) fn prepare(
870	&self,
871	mut replacements: BTreeMap<ExGuid, PropertyObject>,
872	is_section: bool,
873	) -> Result<BTreeMap<ExGuid, PropertyObject>> {
874	let revision = &self.revision;
875	for (id, replacement) in &replacements {
876	if let Some(object) = revision.objects.get(id) {
877	if object.jcid & 0x100000 != 0 {
878	return Err(Error {
879	offset: 0,
880	message: "Read-only object requires a new identity",
881	});
882	}
883	if replacement.jcid != object.jcid
884	|| !matches!(object.data, ObjectData::Properties(_))
885	{
886	return Err(Error {
887	offset: 0,
888	message: "An existing object's type cannot be changed",
889	});
890	}
891	} else if !is_section && replacement.jcid != 0x20001 {
892	return Err(Error {
893	offset: 0,
894	message: "New objects in a table of contents are its entries",
895	});
896	}
897	if replacement.global_ids.keys().any(|i| *i > 0xffffff) {
898	return Err(Error {
899	offset: 0,
900	message: "Invalid property object declaration",
901	});
902	}
903	compact(*id, &replacement.global_ids)?;
904	if is_file_declaration(replacement.jcid) {
905	if !is_section {
906	return Err(Error {
907	offset: 0,
908	message: "File-data objects require a section file",
909	});
910	}
911	file_declaration(&replacement.bytes)?;
912	} else if replacement.jcid & 0x20000 == 0 {
913	return Err(Error {
914	offset: 0,
915	message: "Invalid property object declaration",
916	});
917	} else {
918	PropertySets::parse(&replacement.bytes)?;
919	}
920	}
921	// Native coalescing of duplicate readonly styles can leave dangling references.
922	let mut aliases = BTreeMap::new();
923	for (id, replacement) in &replacements {
924	if revision.objects.contains_key(id)
925	|| replacement.jcid & 0x100000 == 0
926	|| PropertySets::parse(&replacement.bytes)?
927	.sets
928	.iter()
929	.flatten()
930	.any(|p| matches!(p.value, Value::References { .. }))
931	{
932	continue;
933	}
934	let existing = self
935	.readonly
936	.get(&replacement.jcid)
937	.and_then(|contents| contents.get(replacement.bytes.as_slice()))
938	.and_then(|ids| ids.first().copied());
939	let existing = existing.or_else(|| {
940	replacements.range(..id).find_map(|(other, object)| {
941	(object.jcid == replacement.jcid && object.bytes == replacement.bytes)
942	.then_some(*aliases.get(other).unwrap_or(other))
943	})
944	});
945	if let Some(existing) = existing {
946	aliases.insert(*id, existing);
947	}
948	}
949	for id in aliases.keys() {
950	replacements.remove(id);
951	}
952	for object in replacements.values_mut() {
953	if is_file_declaration(object.jcid) {
954	continue;
955	}
956	// The compact IDs this object's table gives aliased identities.
957	let targets: Vec<(u32, ExGuid)> = aliases
958	.iter()
959	.filter(|(id, _)| id.n <= 0xff)
960	.filter_map(|(id, existing)| {
961	let (index, _) = object.global_ids.iter().find(|(_, g)| **g == id.guid)?;
962	Some(((index << 8) | id.n, *existing))
963	})
964	.collect();
965	if targets.is_empty() {
966	continue;
967	}
968	let mut remapped = Vec::new();
969	for property in PropertySets::parse(&object.bytes)?.sets.iter().flatten() {
970	if let Value::References {
971	stream: crate::IdStream::Objects,
972	compact_ids,
973	} = property.value
974	{
975	for bytes in compact_ids.as_chunks::<4>().0 {
976	let raw = u32::from_le_bytes(*bytes);
977	if let Some((_, existing)) = targets.iter().find(|(id, _)| *id == raw) {
978	let offset = bytes.as_ptr().addr() - object.bytes.as_ptr().addr();
979	remapped.push((offset, *existing));
980	}
981	}
982	}
983	}
984	for (offset, id) in remapped {
985	let reference = object.reference(id)?;
986	object.bytes[offset..offset + 4].copy_from_slice(&reference);
987	}
988	}
989	// Detached objects must pass the final reachability check even when unchanged. Equal
990	// bytes are the same object when the table entries they name agree: stored tables
991	// keep only those.
992	let mut unchanged = Vec::new();
993	for (id, replacement) in &replacements {
994	if let Some(object) = revision.objects.get(id)
995	&& self.is_reachable(*id)
996	&& object.data == ObjectData::Properties(&replacement.bytes)
997	&& (Arc::ptr_eq(&object.global_ids, &replacement.global_ids)
998	|| table_entries(&replacement.bytes)?.iter().all(|entry| {
999	object.global_ids.get(entry) == replacement.global_ids.get(entry)
1000	}))
1001	{
1002	unchanged.push(*id);
1003	}
1004	}
1005	for id in unchanged {
1006	replacements.remove(&id);
1007	}
1008	Ok(replacements)
1009	}
1010
1011	/// Stores prepared replacements as the next revision, which checkpoints when the chain
1012	/// would exceed 512 revisions.
1013	pub(crate) fn commit(
1014	&mut self,
1015	replacements: Vec<(ExGuid, crate::Object<'a>)>,
1016	) -> Result<Commit> {
1017	let mut changed = BTreeSet::new();
1018	// Whether each object whose count may move was reachable before.
1019	let mut touched = BTreeMap::new();
1020	let (mut added, mut removed) = (Vec::new(), Vec::new());
1021	for (id, object) in replacements {
1022	changed.insert(id);
1023	let reachable = self.is_reachable(id);
1024	touched.insert(id, reachable);
1025	if reachable {
1026	moved_references(
1027	&self.revision.objects[&id],
1028	&object,
1029	&mut removed,
1030	&mut added,
1031	)?;
1032	}
1033	self.revision.objects.insert(id, object);
1034	}
1035	let roots: BTreeSet<ExGuid> = self.revision.roots.values().copied().collect();
1036	if roots.len() != self.revision.roots.len() {
1037	return Err(Error {
1038	offset: 0,
1039	message: "Object is the root of multiple roles",
1040	});
1041	}
1042	added.extend(
1043	roots
1044	.into_iter()
1045	.filter(|id| !self.incoming.contains_key(id)),
1046	);
1047	// Attaching before detaching keeps a moved subtree from being walked twice.
1048	while let Some(id) = added.pop() {
1049	let object = self.revision.objects.get(&id).ok_or(Error {
1050	offset: 0,
1051	message: "Reachable object has no declaration",
1052	})?;
1053	let count = self.incoming.entry(id).or_default();
1054	touched.entry(id).or_insert(*count > 0);
1055	*count = count.checked_add(1).ok_or(Error {
1056	offset: 0,
1057	message: "Object reference count overflows",
1058	})?;
1059	if *count == 1 {
1060	added.extend(object.references()?.objects);
1061	index(&mut self.readonly, id, object, true);
1062	}
1063	}
1064	while let Some(id) = removed.pop() {
1065	touched.entry(id).or_insert(true);
1066	let count = self.incoming.get_mut(&id).unwrap();
1067	*count -= 1;
1068	if *count == 0 {
1069	self.incoming.remove(&id);
1070	let object = &self.revision.objects[&id];
1071	removed.extend(object.references()?.objects);
1072	index(&mut self.readonly, id, object, false);
1073	}
1074	}
1075	for (&id, &reachable) in &touched {
1076	let count = self.incoming.get(&id).copied();
1077	if changed.contains(&id) && count.is_none() {
1078	return Err(Error {
1079	offset: 0,
1080	message: "Edited object is not reachable in the resulting revision",
1081	});
1082	}
1083	let object = self.revision.objects.get_mut(&id).unwrap();
1084	if (reachable || count.is_some()) && object.reference_count != count.unwrap_or(0) {
1085	object.reference_count = count.unwrap_or(0);
1086	changed.insert(id);
1087	}
1088	}
1089	// Native cold-open fails on long dependency chains; cap their depth at 512.
1090	let checkpoint = self.depth == 0 || self.depth >= 512;
1091	self.depth = if checkpoint { 1 } else { self.depth + 1 };
1092	Ok(Commit {
1093	checkpoint,
1094	changed,
1095	touched: touched.into_keys().collect(),
1096	})
1097	}
1098
1099	/// Gives the objects a revision declares the id tables reading it back yields: objects
1100	/// sharing a table are declared in one group, which keeps the entries they use.
1101	pub(crate) fn settle(&mut self, declared: impl IntoIterator<Item = ExGuid>) -> Result<()> {
1102	let mut groups = BTreeMap::<_, Vec<_>>::new();
1103	for id in declared {
1104	let table = Arc::clone(&self.revision.objects[&id].global_ids);
1105	groups.entry(table).or_default().push(id);
1106	}
1107	for (table, ids) in groups {
1108	let used = used_entries(
1109	&table,
1110	ids.iter().map(|id| (*id, &self.revision.objects[id])),
1111	)?;
1112	if used.iter().eq(table.keys()) {
1113	continue;
1114	}
1115	let kept: Arc<BTreeMap<_, _>> = Arc::new(
1116	table
1117	.iter()
1118	.filter(|(entry, _)| used.binary_search(entry).is_ok())
1119	.map(|(entry, guid)| (*entry, *guid))
1120	.collect(),
1121	);
1122	for id in ids {
1123	self.revision.objects.get_mut(&id).unwrap().global_ids = Arc::clone(&kept);
1124	}
1125	}
1126	Ok(())
1127	}
1128	}
1129
1130	/// Adds a reachable read-only property object to `readonly`, or removes an unreachable one.
1131	fn index<'a>(
1132	readonly: &mut BTreeMap<u32, BTreeMap<&'a [u8], BTreeSet<ExGuid>>>,
1133	id: ExGuid,
1134	object: &crate::Object<'a>,
1135	reachable: bool,
1136	) {
1137	let ObjectData::Properties(bytes) = object.data else {
1138	return;
1139	};
1140	if object.jcid & 0x100000 == 0 {
1141	return;
1142	}
1143	let ids = readonly
1144	.entry(object.jcid)
1145	.or_default()
1146	.entry(bytes)
1147	.or_default();
1148	if reachable {
1149	ids.insert(id);
1150	} else {
1151	ids.remove(&id);
1152	}
1153	}
1154
1155	/// Adds the object references `before` has and `after`, a later version of the object,
1156	/// lacks to `removed`, and those it gains to `added`.
1157	fn moved_references(
1158	before: &crate::Object<'_>,
1159	after: &crate::Object<'_>,
1160	removed: &mut Vec<ExGuid>,
1161	added: &mut Vec<ExGuid>,
1162	) -> Result<()> {
1163	let compact_ids = |object: &crate::Object<'_>| -> Result<Vec<[u8; 4]>> {
1164	let ObjectData::Properties(bytes) = object.data else {
1165	return Ok(Vec::new());
1166	};
1167	let mut ids = Vec::new();
1168	for property in PropertySets::parse(bytes)?.sets.iter().flatten() {
1169	if let Value::References {
1170	stream: crate::IdStream::Objects,
1171	compact_ids,
1172	} = property.value
1173	{
1174	ids.extend(compact_ids.as_chunks::<4>().0.iter().copied());
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
1966	compact_ids.as_chunks::<4>().0.iter().enumerate()
1967	{
1968	let value = u32::from_le_bytes(*value);
1969	let target = ExGuid {
1970	guid: object.global_ids[&(value >> 8)],
1971	n: value & 255,
1972	};
1973	mapped[offset + i * 4..offset + i * 4 + 4]
1974	.copy_from_slice(&compact(target, table)?);
1975	}
1976	}
1977	}
1978	self.append(&mapped)?
1979	} else if sealing.replaced.contains(&id) {
1980	let chunk = match protection {
1981	Some(protection) => {
1982	self.append(&protection.seal_property(bytes)?)?
1983	}
1984	None => self.append(bytes)?,
1985	};
1986	stored.push((id, chunk));
1987	chunk
1988	} else {
1989	located(
1990	segments,
1991	match protection {
1992	Some(protection) => protection.stored(bytes).ok_or(Error {
1993	offset: 0,
1994	message: "Protected object has no stored form",
1995	})?,
1996	None => bytes,
1997	},
1998	)?
1999	};
2000	// A table-of-contents object is declared when the revision is a
2001	// checkpoint or the object is new, and revised otherwise.
2002	let declared = checkpoint || sealing.created.contains(&id);
2003	if is_section {
2004	declaration.extend_from_slice(&object.jcid.to_le_bytes());
2005	declaration.push(flags);
2006	} else if declared {
2007	let body = 1_u64 | (u64::from(flags & 1) << 16);
2008	declaration.extend_from_slice(&body.to_le_bytes()[..6]);
2009	} else {
2010	declaration.extend_from_slice(&u32::from(flags).to_le_bytes());
2011	}
2012	declaration.extend_from_slice(&object.reference_count.to_le_bytes());
2013	let readonly = object.jcid & 0x100000 != 0;
2014	if readonly {
2015	// A protected declaration hashes the plaintext as aligned.
2016	let mut hash = md5::Context::new();
2017	hash.consume(bytes);
2018	if protection.is_some() {
2019	hash.consume(&[0; 7][..(8 - bytes.len() % 8) % 8]);
2020	}
2021	declaration.extend_from_slice(&hash.finalize().0);
2022	}
2023	group.push(node(
2024	if is_section {
2025	if readonly { 0xc5 } else { 0xa5 }
2026	} else if declared {
2027	0x2e
2028	} else {
2029	0x42
2030	},
2031	Some(Reference::Data(data)),
2032	&declaration,
2033	)?);
2034	}
2035	ObjectData::Encrypted(_) => {
2036	return Err(Error {
2037	offset: 0,
2038	message: "Encrypted objects cannot be checkpointed",
2039	});
2040	}
2041	}
2042	}
2043	if is_section {
2044	group.push(node(0xb8, None, &[])?);
2045	let (chunk, _) = self.list(&group)?;
2046	manifest.push(node(0xb0, Some(Reference::NodeList(chunk)), &payload)?);
2047	let mut overrides = vec![0; 8];
2048	overrides.extend_from_slice(&(!override_crc).to_le_bytes());
2049	manifest.push(node(
2050	0x84,
2051	Some(Reference::Data(Chunk {
2052	offset: u64::MAX,
2053	length: 0,
2054	})),
2055	&overrides,
2056	)?);
2057	} else {
2058	manifest.extend(group);
2059	}
2060	}
2061	if checkpoint {
2062	for (role, id) in &revision.roots {
2063	let mut payload = Vec::new();
2064	if is_section {
2065	id.encode(&mut payload);
2066	} else {
2067	payload.extend_from_slice(&compact(*id, toc_table.as_ref().unwrap())?);
2068	}
2069	payload.extend_from_slice(&role.to_le_bytes());
2070	manifest.push(node(if is_section { 0x5a } else { 0x59 }, None, &payload)?);
2071	}
2072	}
2073	manifest.push(node(0x1c, None, &[])?);
2074	Ok((new_rid, stored))
2075	}
2076
2077	/// Adds a space's manifest nodes to its revision list, creating the space when `new`.
2078	pub(crate) fn close(&mut self, space: ExGuid, new: bool, manifest: &[Vec<u8>]) -> Result<()> {
2079	if new {
2080	let (chunk, tail) = self.list(manifest)?;
2081	let mut payload = Vec::new();
2082	space.encode(&mut payload);
2083	let (chunk, _) = self.list(&[
2084	node(0xc, None, &payload)?,
2085	node(0x10, Some(Reference::NodeList(chunk)), &[])?,
2086	])?;
2087	self.root_nodes
2088	.push(node(8, Some(Reference::NodeList(chunk)), &payload)?);
2089	self.state.spaces.insert(space, tail);
2090	} else {
2091	let mut tail = *self.state.spaces.get(&space).ok_or(Error {
2092	offset: 0,
2093	message: "Object space is absent from the root list",
2094	})?;
2095	self.extend(&mut tail, manifest)?;
2096	self.state.spaces.insert(space, tail);
2097	}
2098	Ok(())
2099	}
2100
2101	/// Embeds payloads as file-data store objects referenced from the root file node list
2102	/// under their identities, as OneNote embeds pictures and attachments.
2103	pub(crate) fn payloads(
2104	&mut self,
2105	payloads: &[([u8; 16], &[u8])],
2106	protection: Option<&dyn Protection>,
2107	) -> Result<()> {
2108	let mut data_nodes = Vec::new();
2109	for (guid, payload) in payloads {
2110	if self.state.file_type != FileType::Section {
2111	return Err(Error {
2112	offset: 0,
2113	message: "Embedded payloads require a section file",
2114	});
2115	}
2116	let mut blob = vec![
2117	0xe7, 0x16, 0xe3, 0xbd, 0x65, 0x26, 0x11, 0x45, 0xa4, 0xc4, 0x8d, 0x4d, 0x0b, 0x7a,
2118	0x9e, 0xac,
2119	];
2120	let sealed = protection
2121	.map(|protection| protection.seal_file(payload))
2122	.transpose()?;
2123	let payload = sealed.as_deref().unwrap_or(*payload);
2124	blob.extend_from_slice(&(payload.len() as u64).to_le_bytes());
2125	blob.extend_from_slice(&[0; 12]);
2126	blob.extend_from_slice(payload);
2127	blob.resize(blob.len().next_multiple_of(8), 0);
2128	blob.extend_from_slice(&[
2129	0x22, 0xa7, 0xfb, 0x71, 0x79, 0x0f, 0x0b, 0x4a, 0xbb, 0x13, 0x89, 0x92, 0x56, 0x42,
2130	0x6b, 0x24,
2131	]);
2132	let chunk = self.append(&blob)?;
2133	data_nodes.push(node(0x94, Some(Reference::Data(chunk)), guid)?);
2134	}
2135	if data_nodes.is_empty() {
2136	return Ok(());
2137	}
2138	// Payload declarations live in the file-data store list the root list references.
2139	match self.state.files {
2140	Some(mut tail) => {
2141	self.extend(&mut tail, &data_nodes)?;
2142	self.state.files = Some(tail);
2143	}
2144	None => {
2145	let (chunk, tail) = self.list(&data_nodes)?;
2146	self.state.files = Some(tail);
2147	self.root_nodes
2148	.push(node(0x90, Some(Reference::NodeList(chunk)), &[])?);
2149	}
2150	}
2151	Ok(())
2152	}
2153
2154	/// The transaction committing what was appended, and the state it leaves; none when
2155	/// nothing was.
2156	pub(crate) fn finish(mut self) -> Result<Option<(crate::Transaction, StoreState)>> {
2157	if !self.root_nodes.is_empty() {
2158	let nodes = std::mem::take(&mut self.root_nodes);
2159	let mut root = self.state.root;
2160	self.extend(&mut root, &nodes)?;
2161	self.state.root = root;
2162	}
2163	if self.counts.is_empty() {
2164	return Ok(None);
2165	}
2166	let file_type = self.state.file_type;
2167	let is_section = file_type == FileType::Section;
2168	let mut header = self.base.header;
2169	let count = u32::from_le_bytes(header[96..100].try_into().unwrap());
2170	let transactions = count.checked_add(1).ok_or(Error {
2171	offset: 96,
2172	message: "Transaction counter is exhausted",
2173	})?;
2174	let changed_bytes = count ^ transactions;
2175	let commit_byte = (31 - changed_bytes.leading_zeros()) / 8;
2176	let ceiling = transactions | ((1_u32 << (commit_byte * 8)) - 1);
2177	let mut entries = Vec::new();
2178	for (id, count) in std::mem::take(&mut self.counts) {
2179	entries.extend_from_slice(&id.to_le_bytes());
2180	entries.extend_from_slice(
2181	&u32::try_from(count)
2182	.map_err(|_| Error {
2183	offset: 0,
2184	message: "File-node count exceeds the format limit",
2185	})?
2186	.to_le_bytes(),
2187	);
2188	}
2189	let (mut log_chunk, mut used) = self.state.log;
2190	let mut checksum = self.state.log_crc;
2191	let mut crc_used = used;
2192	let mut crc_capacity = (log_chunk.length as usize - 12) & !7;
2193	let mut advance_crc = |checksum, entry: &[u8]| {
2194	if crc_used == crc_capacity {
2195	crc_used = 0;
2196	crc_capacity = 1008;
2197	}
2198	crc_used += 8;
2199	transaction_crc(checksum, entry, file_type, crc_used == crc_capacity)
2200	};
2201	for entry in entries.as_chunks::<8>().0 {
2202	checksum = advance_crc(checksum, entry);
2203	}
2204	// Past a counter carry, sentinels up to the ceiling follow the one that commits; the
2205	// next transaction's entries overwrite them, as a reader counting sentinels expects.
2206	let committed = entries.len() + 8;
2207	let mut committed_crc = None;
2208	for _ in transactions..=ceiling {
2209	let sentinel_crc = if is_section { !checksum } else { checksum };
2210	entries.extend_from_slice(&1_u32.to_le_bytes());
2211	entries.extend_from_slice(&sentinel_crc.to_le_bytes());
2212	checksum = advance_crc(checksum, &entries[entries.len() - 8..]);
2213	committed_crc.get_or_insert(checksum);
2214	}
2215	let mut log = self.state.log;
2216	let mut remaining = entries.as_slice();
2217	while !remaining.is_empty() {
2218	let capacity = usize::try_from(log_chunk.length)
2219	.unwrap()
2220	.checked_sub(12)
2221	.map(|size| size & !7)
2222	.filter(|capacity| *capacity >= used)
2223	.ok_or(Error {
2224	offset: usize::try_from(log_chunk.offset).unwrap(),
2225	message: "Transaction fragment has no room for continuation",
2226	})?;
2227	let size = remaining.len().min(capacity - used);
2228	self.write(log_chunk.offset + used as u64, &remaining[..size]);
2229	let written = entries.len() - remaining.len();
2230	if (written + 1..=written + size).contains(&committed) {
2231	log = (log_chunk, used + committed - written);
2232	}
2233	used += size;
2234	remaining = &remaining[size..];
2235	if !remaining.is_empty() {
2236	let mut fragment = vec![0; 1024];
2237	fragment[1008..1016].copy_from_slice(&u64::MAX.to_le_bytes());
2238	let next = self.append(&fragment)?;
2239	let mut reference = next.offset.to_le_bytes().to_vec();
2240	reference.extend_from_slice(&(next.length as u32).to_le_bytes());
2241	self.write(log_chunk.offset + capacity as u64, &reference);
2242	log_chunk = next;
2243	used = 0;
2244	}
2245	}
2246	let length = self.end();
2247	header[96..100].copy_from_slice(&transactions.to_le_bytes());
2248	header[196..204].copy_from_slice(&length.to_le_bytes());
2249	header[212..228].copy_from_slice(&fresh_guid()?);
2250	header[236..252].copy_from_slice(&fresh_guid()?);
2251	let generation = u64::from_le_bytes(header[228..236].try_into().unwrap())
2252	.checked_add(1)
2253	.ok_or(Error {
2254	offset: 228,
2255	message: "File generation counter is exhausted",
2256	})?;
2257	header[228..236].copy_from_slice(&generation.to_le_bytes());
2258	self.state.stamp = crate::Stamp { header, length };
2259	self.state.log = log;
2260	self.state.log_crc = committed_crc.unwrap();
2261	Ok(Some((
2262	crate::Transaction {
2263	base: self.base,
2264	append: self.append,
2265	patches: self.patches,
2266	header,
2267	},
2268	self.state,
2269	)))
2270	}
2271	}
2272
2273	/// The `required` nodes of fragment `sequence` of list `id`, which `bytes` at `at` hold and
2274	/// which ends its list.
2275	fn nodes(
2276	bytes: &[u8],
2277	at: Chunk,
2278	id: u32,
2279	sequence: u32,
2280	required: usize,
2281	) -> Result<Vec<Node<'_>>> {
2282	let fragment = Fragment::parse(bytes, at.offset as usize)?;
2283	if fragment.id != id || fragment.sequence != sequence || !fragment.next.absent() {
2284	return Err(Error {
2285	offset: at.offset as usize,
2286	message: "An appended fragment has the wrong list, sequence or successor",
2287	});
2288	}
2289	let mut nodes = Vec::new();
2290	fragment.nodes(required, &mut nodes, |_| Ok(()))?;
2291	if nodes.len() != required {
2292	return Err(Error {
2293	offset: at.offset as usize,
2294	message: "An appended fragment lacks logged nodes",
2295	});
2296	}
2297	Ok(nodes)
2298	}
2299
2300	/// A revision `Appending::revision` wrote, as `check_transaction` expects to read it back.
2301	pub(crate) struct Written<'r, 'a> {
2302	pub space: ExGuid,
2303	pub rid: ExGuid,
2304	pub previous: Option<ExGuid>,
2305	pub label: (ExGuid, u32),
2306	pub live: &'r LiveRevision<'a>,
2307	pub commit: &'r Commit,
2308	}
2309
2310	/// Reads back what `transaction` appends to the section `before` describes, whose bytes
2311	/// `segments` hold, and checks it stores `revisions`, then each space's `labels` (space,
2312	/// revision, context), and `payloads` as `after` expects:
2313	/// fragments link and decode to the logged counts under the logged checksum; each declared
2314	/// object parses, names identities its group's table holds and objects reachable after its
2315	/// revision, carries its incremental reference count and, if read-only, its MD5; roots stay
2316	/// unless a space is new. Validates nothing the transaction leaves as it was.
2317	#[allow(clippy::too_many_arguments)]
2318	pub(crate) fn check_transaction(
2319	before: &StoreState,
2320	after: &StoreState,
2321	transaction: &crate::Transaction,
2322	segments: &[(u64, &[u8])],
2323	revisions: &[Written<'_, '_>],
2324	labels: &[(ExGuid, ExGuid, ExGuid)],
2325	payloads: &[([u8; 16], &[u8])],
2326	protection: Option<&dyn Protection>,
2327	) -> Result<()> {
2328	let wrong = |message| Error { offset: 0, message };
2329	let encoding: [u8; 2] = if protection.is_some() { [2, 0] } else { [0, 0] };
2330	let base = transaction.base.length;
2331	// A chunk's bytes with this transaction's writes: nothing read here is patched earlier.
2332	let read = |chunk: Chunk| -> Result<Vec<u8>> {
2333	let (start, end) = (chunk.offset, chunk.offset + chunk.length);
2334	let mut bytes = if start >= base {
2335	transaction
2336	.append
2337	.get((start - base) as usize..(end - base) as usize)
2338	.ok_or(wrong("An appended chunk lies outside the transaction"))?
2339	.to_vec()
2340	} else {
2341	let (offset, segment) = segments
2342	.iter()
2343	.rfind(|(offset, _)| *offset <= start)
2344	.ok_or(wrong("A chunk lies outside the store"))?;
2345	segment
2346	.get((start - offset) as usize..(end - offset) as usize)
2347	.ok_or(wrong("A chunk lies outside the store"))?
2348	.to_vec()
2349	};
2350	for (offset, patch) in &transaction.patches {
2351	let (from, to) = (start.max(*offset), end.min(offset + patch.len() as u64));
2352	if from < to {
2353	bytes[(from - start) as usize..(to - start) as usize]
2354	.copy_from_slice(&patch[(from - offset) as usize..(to - offset) as usize]);
2355	}
2356	}
2357	Ok(bytes)
2358	};
2359	let header = &transaction.header;
2360	let count = |header: &[u8; 1024]| u32::from_le_bytes(header[96..100].try_into().unwrap());
2361	if *header != after.stamp.header
2362	|| count(header) != count(&before.stamp.header) + 1
2363	|| u64::from_le_bytes(header[196..204].try_into().unwrap()) != after.stamp.length
2364	|| after.stamp.length != base + transaction.append.len() as u64
2365	{
2366	return Err(wrong("The transaction header does not commit its bytes"));
2367	}
2368
2369	// The log: entries from where it ended, through the sentinel that commits them.
2370	let mut counts = BTreeMap::new();
2371	let (mut chunk, mut used) = before.log;
2372	let mut checksum = before.log_crc;
2373	loop {
2374	let capacity = (chunk.length as usize - 12) & !7;
2375	let bytes = read(chunk)?;
2376	if used == capacity {
2377	let next = u64::from_le_bytes(bytes[capacity..capacity + 8].try_into().unwrap());
2378	let length = u32::from_le_bytes(bytes[capacity + 8..capacity + 12].try_into().unwrap());
2379	(chunk, used) = (
2380	Chunk {
2381	offset: next,
2382	length: u64::from(length),
2383	},
2384	0,
2385	);
2386	continue;
2387	}
2388	let entry = &bytes[used..used + 8];
2389	used += 8;
2390	let id = u32::from_le_bytes(entry[..4].try_into().unwrap());
2391	let value = u32::from_le_bytes(entry[4..].try_into().unwrap());
2392	if id == 1 {
2393	if value != !checksum {
2394	return Err(wrong("The transaction log checksum does not match"));
2395	}
2396	checksum = transaction_crc(checksum, entry, FileType::Section, used == capacity);
2397	break;
2398	}
2399	checksum = transaction_crc(checksum, entry, FileType::Section, used == capacity);
2400	counts.insert(id, value as usize);
2401	}
2402	if (chunk, used) != after.log || checksum != after.log_crc {
2403	return Err(wrong("The transaction log ends elsewhere than its state"));
2404	}
2405
2406	// Nodes a list gained: the fragment `after` ends with, linked from where `before` ended.
2407	let gained = |before: Option<&ListTail>, after: &ListTail| -> Result<Vec<u8>> {
2408	if counts.get(&after.id) != Some(&after.nodes) {
2409	return Err(wrong("A list's nodes disagree with the transaction log"));
2410	}
2411	if let Some(before) = before {
2412	let previous = read(before.last)?;
2413	if Fragment::parse(&previous, before.last.offset as usize)?.next != after.last
2414	|| after.fragments != before.fragments + 1
2415	|| after.id != before.id
2416	{
2417	return Err(wrong("An appended fragment is not linked to its list"));
2418	}
2419	}
2420	read(after.last)
2421	};
2422	// Each space's list gains one fragment: its revisions in order, then its labels.
2423	let mut spaces: Vec<ExGuid> = Vec::new();
2424	for space in revisions
2425	.iter()
2426	.map(|written| written.space)
2427	.chain(labels.iter().map(|(space, ..)| *space))
2428	{
2429	if !spaces.contains(&space) {
2430	spaces.push(space);
2431	}
2432	}
2433	for space in spaces {
2434	let old = before.spaces.get(&space);
2435	let new = after
2436	.spaces
2437	.get(&space)
2438	.ok_or(wrong("A sealed space has no list"))?;
2439	let bytes = gained(old, new)?;
2440	let manifest = nodes(
2441	&bytes,
2442	new.last,
2443	new.id,
2444	old.map_or(0, |old| old.fragments),
2445	new.nodes - old.map_or(0, |old| old.nodes),
2446	)?;
2447	let mut manifest = manifest.iter();
2448	let mut next = || {
2449	manifest
2450	.next()
2451	.ok_or(wrong("A revision manifest is truncated"))
2452	};
2453	let mut fresh = old.is_none();
2454	for written in revisions.iter().filter(|written| written.space == space) {
2455	let Written {
2456	rid,
2457	live,
2458	commit,
2459	label,
2460	..
2461	} = *written;
2462	let mut node = next()?;
2463	if fresh {
2464	let mut c = Cursor {
2465	bytes: node.payload,
2466	offset: node.offset,
2467	};
2468	if node.id != 0x14 || c.exguid()? != space {
2469	return Err(wrong("A new space's revision list names another space"));
2470	}
2471	node = next()?;
2472	fresh = false;
2473	}
2474	let mut c = Cursor {
2475	bytes: node.payload,
2476	offset: node.offset,
2477	};
2478	let dependency = if commit.checkpoint {
2479	ExGuid::default()
2480	} else {
2481	written
2482	.previous
2483	.ok_or(wrong("A dependent revision follows none"))?
2484	};
2485	let contextual = label.0 != ExGuid::default();
2486	if node.id != if contextual { 0x1f } else { 0x1e }
2487	|| c.exguid()? != rid
2488	|| c.exguid()? != dependency
2489	|| c.read::<4>()? != label.1.to_le_bytes()
2490	|| c.read::<2>()? != encoding
2491	|| (contextual && c.exguid()? != label.0)
2492	{
2493	return Err(wrong(
2494	"A revision starts with the wrong identity, dependency or label",
2495	));
2496	}
2497	if let Some(protection) = protection {
2498	let node = next()?;
2499	if node.id != 0x7c || node.reference != Some(Reference::Data(protection.metadata()))
2500	{
2501	return Err(wrong("A protected revision does not name its key"));
2502	}
2503	}
2504	let mut declared = BTreeSet::new();
2505	let mut roots = BTreeMap::new();
2506	loop {
2507	let node = next()?;
2508	match node.id {
2509	0xb0 => {
2510	let Some(Reference::NodeList(at)) = node.reference else {
2511	return Err(wrong("An object group lacks its list"));
2512	};
2513	let bytes = read(at)?;
2514	let id = Fragment::parse(&bytes, at.offset as usize)?.id;
2515	let required = *counts
2516	.get(&id)
2517	.ok_or(wrong("An object group is not logged"))?;
2518	let group = nodes(&bytes, at, id, 0, required)?;
2519	let mut table = BTreeMap::new();
2520	let mut override_crc = u32::MAX;
2521	for item in &group {
2522	let mut c = Cursor {
2523	bytes: item.payload,
2524	offset: item.offset,
2525	};
2526	match item.id {
2527	0xb4 | 0x22 | 0x28 | 0xb8 => {}
2528	0x24 => {
2529	table.insert(u32::from_le_bytes(c.read()?), c.read::<16>()?);
2530	}
2531	0xa5 | 0xc5 | 0x73 => {
2532	let id = c.compact(&table)?;
2533	let object =
2534	live.revision.objects.get(&id).ok_or(wrong(
2535	"A revision declares an unknown object",
2536	))?;
2537	let jcid = u32::from_le_bytes(c.read()?);
2538	let flags = if item.id == 0x73 {
2539	None
2540	} else {
2541	Some(c.read::<1>()?[0])
2542	};
2543	let count = u32::from_le_bytes(c.read()?);
2544	if !declared.insert(id)
2545	|| jcid != object.jcid
2546	|| count != object.reference_count
2547	{
2548	return Err(wrong(
2549	"A declaration disagrees with its object or its count",
2550	));
2551	}
2552	override_crc =
2553	crc(override_crc, &count.to_le_bytes(), FileType::Section);
2554	if item.id == 0x73 {
2555	continue;
2556	}
2557	let Some(Reference::Data(at)) = item.reference else {
2558	return Err(wrong("An object declaration lacks its data"));
2559	};
2560	let data = read(at)?;
2561	let clear = match protection {
2562	Some(protection) => protection.open_property(&data)?,
2563	None => zeroize::Zeroizing::new(data.clone()),
2564	};
2565	let stored = crate::Object {
2566	jcid,
2567	reference_count: count,
2568	data: ObjectData::Properties(&clear),
2569	global_ids: Arc::new(table.clone()),
2570	};
2571	let references = stored.references()?;
2572	let expected = u8::from(!references.objects.is_empty())
2573	| (u8::from(
2574	!references.object_spaces.is_empty()
2575	|| !references.contexts.is_empty(),
2576	) << 1);
2577	let hash = match protection {
2578	Some(_) => crate::protected::digest(&clear),
2579	None => md5::compute(&data).0,
2580	};
2581	if object.data != ObjectData::Properties(&clear)
2582	|| flags != Some(expected)
2583	|| (item.id == 0xc5) != (jcid & 0x100000 != 0)
2584	|| (item.id == 0xc5 && c.read::<16>()? != hash)
2585	{
2586	return Err(wrong(
2587	"An object's stored bytes differ from its revision",
2588	));
2589	}
2590	if live.is_reachable(id)
2591	&& !references
2592	.objects
2593	.iter()
2594	.all(|target| live.is_reachable(*target))
2595	{
2596	return Err(wrong(
2597	"An object references one its revision cannot reach",
2598	));
2599	}
2600	}
2601	_ => return Err(wrong("Unexpected node in an object group")),
2602	}
2603	}
2604	let node = next()?;
2605	let mut c = Cursor {
2606	bytes: node.payload,
2607	offset: node.offset,
2608	};
2609	if node.id != 0x84
2610	|| c.read::<8>()? != [0; 8]
2611	|| u32::from_le_bytes(c.read()?) != !override_crc
2612	{
2613	return Err(wrong("An object group's count overrides do not match"));
2614	}
2615	}
2616	0x5a => {
2617	let mut c = Cursor {
2618	bytes: node.payload,
2619	offset: node.offset,
2620	};
2621	let id = c.exguid()?;
2622	roots.insert(u32::from_le_bytes(c.read()?), id);
2623	}
2624	0x1c => break,
2625	_ => return Err(wrong("Unexpected node in a revision manifest")),
2626	}
2627	}
2628	let expected: BTreeSet<ExGuid> = if commit.checkpoint {
2629	live.revision.objects.keys().copied().collect()
2630	} else {
2631	commit.changed.clone()
2632	};
2633	if declared != expected
2634	|| (commit.checkpoint && roots != live.revision.roots)
2635	|| (!commit.checkpoint && !roots.is_empty())
2636	{
2637	return Err(wrong(
2638	"A revision declares other objects or roots than it changed",
2639	));
2640	}
2641	}
2642	for (_, rid, context) in labels.iter().filter(|(labelled, ..)| *labelled == space) {
2643	let node = next()?;
2644	if node.id != 0x5d || node.payload != label_payload(*rid, *context) {
2645	return Err(wrong("A revision label names another revision or context"));
2646	}
2647	}
2648	if next().is_ok() {
2649	return Err(wrong(
2650	"A revision list gains nodes no revision or label declares",
2651	));
2652	}
2653	}
2654
2655	if after.root.nodes != before.root.nodes {
2656	let bytes = gained(Some(&before.root), &after.root)?;
2657	let added = nodes(
2658	&bytes,
2659	after.root.last,
2660	after.root.id,
2661	before.root.fragments,
2662	after.root.nodes - before.root.nodes,
2663	)?;
2664	let created = revisions
2665	.iter()
2666	.map(|written| written.space)
2667	.filter(|space| !before.spaces.contains_key(space))
2668	.collect::<BTreeSet<_>>()
2669	.len();
2670	let spaces = added.iter().filter(|node| node.id == 8).count();
2671	if spaces != created || added.iter().any(|node| !matches!(node.id, 8 | 0x90)) {
2672	return Err(wrong(
2673	"The root list gains other nodes than new spaces declare",
2674	));
2675	}
2676	}
2677	if !payloads.is_empty() {
2678	let files = after
2679	.files
2680	.as_ref()
2681	.ok_or(wrong("Embedded payloads have no store"))?;
2682	let bytes = gained(before.files.as_ref(), files)?;
2683	let declared = nodes(
2684	&bytes,
2685	files.last,
2686	files.id,
2687	before.files.map_or(0, |files| files.fragments),
2688	payloads.len(),
2689	)?;
2690	for ((guid, payload), node) in payloads.iter().zip(&declared) {
2691	let Some(Reference::Data(at)) = node.reference else {
2692	return Err(wrong("A payload declaration lacks its data"));
2693	};
2694	let data = read(at)?;
2695	let blob = crate::files::payload(&data, at.offset as usize)?;
2696	let blob = match protection {
2697	Some(protection) => protection.open_file(blob)?,
2698	None => zeroize::Zeroizing::new(blob.to_vec()),
2699	};
2700	if node.id != 0x94 || node.payload != guid || blob.as_slice() != *payload {
2701	return Err(wrong("An embedded payload differs from its declaration"));
2702	}
2703	}
2704	}
2705	Ok(())
2706	}