oxedyne/daimond — src/diamond

26.4 KiB, 1 run

created by r2519314175:939, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1	//! Crystal version history as a delta log: what is stored at each version, and
2	//! which stored files rebuild any one of them.
3	//!
4	//! Every capp page edit used to write a full uncompressed copy of the page into
5	//! `versions/`, and nothing anywhere prunes them. The shipped Log Life page is
6	//! 101,834 bytes, so a hundred edits was 10.2 MB against a per-Diamond share of
7	//! 4 MiB -- and the daimon had already computed the difference twice by then and
8	//! thrown it away both times.
9	//!
10	//! So a version stores either a full copy, called a KEYFRAME, or the splices
11	//! from the snapshot before it, called a PATCH. One keyframe every
12	//! [`KEYFRAME_EVERY`] versions bounds two things that rebuild time does not:
13	//! how much history one bad patch can invalidate, and how many files the history
14	//! view reads to answer a question about an old version.
15	//!
16	//! The OPFS edge that reads and writes the files lives in
17	//! [`crate::wasm::diamond`], which is compiled only for wasm32 and so cannot be
18	//! reached by the native test suite. What decides -- when a keyframe is due,
19	//! which files rebuild version N, and whether a patch may be recorded at all --
20	//! sits here instead, where it is tested against the real page.
21	//!
22	//! # Why nothing here can record a delta that will not read back
23	//!
24	//! [`record`] never returns a patch it has not already applied. It gets its
25	//! patch from [`oxedyne_fe2o3_ore::diff::make_patch`], which decodes and applies
26	//! what it just encoded and refuses to return anything whose reconstruction is
27	//! not the bytes it was given; and where that refuses, [`record`] falls back to
28	//! the full copy the store wrote before this module existed. A patch is
29	//! therefore either provably reconstructible or not written, and the failure
30	//! mode of every fault in the diff, the encoding and the decoding is one
31	//! keyframe -- which costs space and loses nothing.
32
33	use oxedyne_fe2o3_core::prelude::*;
34	use oxedyne_fe2o3_ore::diff;
35
36
37	/// How many versions one full copy has to serve.
38	///
39	/// Not bought by rebuild time, which is negligible -- a thousand-deep chain
40	/// rebuilds in about two milliseconds. Bought by blast radius, because one bad
41	/// patch invalidates every version back to the keyframe before it, and by the
42	/// history view, which reads the whole chain to show one old version. Twenty
43	/// bounds the loss at twenty versions and costs five per cent of one full copy
44	/// per version.
45	pub const KEYFRAME_EVERY: usize = 20;
46
47
48	/// What one stored snapshot is.
49	#[derive(Clone, Copy, Debug, Eq, PartialEq)]
50	pub enum Snap {
51	Keyframe, // the file's whole bytes
52	Patch, // splices from the snapshot before this one
53	}
54
55	/// What [`record`] decided to store, and the bytes to store.
56	#[derive(Clone, Debug, Eq, PartialEq)]
57	pub enum Recorded {
58	Keyframe(Vec<u8>),
59	Patch(Vec<u8>),
60	}
61
62	impl Recorded {
63	pub fn bytes(&self) -> &[u8] {
64	match self {
65	Self::Keyframe(b) => b,
66	Self::Patch(b) => b,
67	}
68	}
69
70	pub fn snap(&self) -> Snap {
71	match self {
72	Self::Keyframe(_) => Snap::Keyframe,
73	Self::Patch(_) => Snap::Patch,
74	}
75	}
76
77	/// Does this hold splices rather than a whole file?
78	pub fn is_patch(&self) -> bool {
79	matches!(self, Self::Patch(_))
80	}
81	}
82
83
84	/// Is the next snapshot due to be a full copy?
85	///
86	/// True where there is no full copy to build on at all, and true where
87	/// [`KEYFRAME_EVERY`] - 1 patches already stand between the newest snapshot and
88	/// the keyframe under them -- so a chain is never longer than that, and one
89	/// version in [`KEYFRAME_EVERY`] is a full copy.
90	///
91	/// Counted over the snapshots rather than taken from the version number,
92	/// because the page is snapshotted only where it changed: its versions are
93	/// sparse and arbitrary, and `N % 20` over them would put keyframes wherever
94	/// the user happened to edit.
95	pub fn wants_keyframe(snaps: &[(u64, Snap)]) -> bool {
96	let mut sorted: Vec<(u64, Snap)> = snaps.to_vec();
97	sorted.sort_by_key(\|(n, _)\| *n);
98	let last_kf = sorted.iter().rposition(\|(_, s)\| *s == Snap::Keyframe);
99	match last_kf {
100	None => true,
101	Some(at) => sorted.len() - 1 - at >= KEYFRAME_EVERY - 1,
102	}
103	}
104
105	/// What to store for a new version of a file, given the file as it stood at the
106	/// snapshot before it and the snapshots already held.
107	///
108	/// **A patch comes back only when it has already been applied and the result
109	/// compared with `new`.** That check is inside
110	/// [`oxedyne_fe2o3_ore::diff::make_patch`], which refuses rather than returning
111	/// a patch whose reconstruction is not the bytes it was handed, and every
112	/// refusal lands here as a keyframe. The failure mode of the whole delta log is
113	/// therefore the full copy the store wrote before it existed.
114	///
115	/// A patch no smaller than the file is refused as well, so a version whose
116	/// content was replaced wholesale costs a full copy and not a full copy plus a
117	/// header.
118	///
119	/// # Arguments
120	/// * `parent` - The file as at the snapshot before this one, or `None` where
121	/// there is no snapshot before it or it could not be rebuilt.
122	/// * `new` - The file as it now stands.
123	/// * `snaps` - Every snapshot already held for this file, in any order.
124	pub fn record(parent: Option<&[u8]>, new: &[u8], snaps: &[(u64, Snap)]) -> Recorded {
125	let old = match parent {
126	Some(o) if !wants_keyframe(snaps) => o,
127	_ => return Recorded::Keyframe(new.to_vec()),
128	};
129	match diff::make_patch(old, new) {
130	Ok(p) if p.len() < new.len() => Recorded::Patch(p),
131	_ => Recorded::Keyframe(new.to_vec()),
132	}
133	}
134
135	/// Which snapshots rebuild the file as at exactly `want`, keyframe first.
136	///
137	/// For the crystal's memory, which is snapshotted at every version. A version
138	/// with no snapshot of its own is an error and not a walk back to an older one:
139	/// answering "what did this hold at v12" with v9's bytes, silently, is the one
140	/// failure a delta log must not have.
141	pub fn plan_at(snaps: &[(u64, Snap)], want: u64)
142	-> Outcome<Vec<u64>>
143	{
144	let sorted = sorted(snaps);
145	let at = match sorted.iter().position(\|(n, _)\| *n == want) {
146	Some(i) => i,
147	None => return Err(err!(
148	"Version {} has no snapshot of its own, and the versions either side of it are \
149	not it.", want; Missing, Data)),
150	};
151	back_to_keyframe(&sorted, at, want)
152	}
153
154	/// Which snapshots rebuild the file as at the newest version at or before
155	/// `want`, keyframe first, and which version that is.
156	///
157	/// For the page, which is snapshotted only where it changed, so most versions
158	/// have none and asking for one of those is asking for whatever page was on
159	/// screen at the time. `None` means nothing was ever stored at or before
160	/// `want`, which is what every version from before there were pages says.
161	pub fn plan_upto(snaps: &[(u64, Snap)], want: u64)
162	-> Outcome<Option<(u64, Vec<u64>)>>
163	{
164	let sorted = sorted(snaps);
165	let at = match sorted.iter().rposition(\|(n, _)\| *n <= want) {
166	Some(i) => i,
167	None => return Ok(None),
168	};
169	let target = sorted[at].0;
170	Ok(Some((target, res!(back_to_keyframe(&sorted, at, target)))))
171	}
172
173	/// Rebuild a file from the keyframe and the patches after it, in the order
174	/// [`plan_at`] and [`plan_upto`] gave them.
175	///
176	/// Every patch names the length and the checksum of what it was made against
177	/// and of what it makes, so a chain assembled in the wrong order, one missing a
178	/// link, or one carrying a decayed file, is refused at the link that is wrong.
179	/// Nothing here returns a partial rebuild, and in particular nothing returns
180	/// the keyframe when the patches over it could not be applied.
181	pub fn materialise(keyframe: Vec<u8>, patches: &[Vec<u8>])
182	-> Outcome<Vec<u8>>
183	{
184	let mut at = keyframe;
185	for (i, p) in patches.iter().enumerate() {
186	at = match diff::apply_patch(&at, p) {
187	Ok(b) => b,
188	Err(e) => return Err(err!(e,
189	"Patch {} of {} in this version's chain could not be applied to the {} \
190	bytes under it.", i + 1, patches.len(), at.len(); Invalid, Data)),
191	};
192	}
193	Ok(at)
194	}
195
196	fn sorted(snaps: &[(u64, Snap)]) -> Vec<(u64, Snap)> {
197	let mut out: Vec<(u64, Snap)> = snaps.to_vec();
198	out.sort_by_key(\|(n, _)\| *n);
199	out
200	}
201
202	/// The run from the last keyframe at or below `at` up to `at` inclusive.
203	fn back_to_keyframe(sorted: &[(u64, Snap)], at: usize, want: u64)
204	-> Outcome<Vec<u64>>
205	{
206	let mut i = at;
207	loop {
208	if sorted[i].1 == Snap::Keyframe {
209	return Ok(sorted[i..=at].iter().map(\|(n, _)\| *n).collect());
210	}
211	if i == 0 {
212	return Err(err!(
213	"Version {} is built on patches all the way back to version {}, and there is \
214	no full copy under them.", want, sorted[0].0; Missing, Data));
215	}
216	i -= 1;
217	}
218	}
219
220
221	#[cfg(test)]
222	mod tests {
223	use super::*;
224
225	use std::collections::HashMap;
226
227	/// The shipped Log Life page, 101,834 bytes: the file `versions/` is
228	/// actually full of, and the one the owner's own Diamond has been
229	/// accumulating full copies of. A fixture shaped by hand would flatter the
230	/// diff; this is the real thing, its real CSS, its real script and its real
231	/// repeated markup.
232	const PAGE: &str = include_str!("../www/capps/lifelog/crystal.html");
233
234	/// A whole stored history for one file: what each version holds, and what a
235	/// reader gets back for it.
236	///
237	/// Not a mock. These are [`record`], [`plan_at`] and [`materialise`]
238	/// themselves, with the OPFS calls replaced by a map -- which is exactly
239	/// what [`crate::wasm::diamond`] puts round them.
240	struct Log {
241	held: Vec<(u64, Snap)>,
242	bytes: HashMap<u64, Vec<u8>>,
243	}
244
245	impl Log {
246	fn new() -> Self {
247	Self { held: Vec::new(), bytes: HashMap::new() }
248	}
249
250	fn write(&mut self, version: u64, content: &[u8])
251	-> Outcome<Snap>
252	{
253	let parent = match self.held.iter().map(\|(n, _)\| *n).max() {
254	Some(p) => Some(res!(self.read(p))),
255	None => None,
256	};
257	let rec = record(parent.as_deref(), content, &self.held);
258	self.bytes.insert(version, rec.bytes().to_vec());
259	self.held.push((version, rec.snap()));
260	Ok(rec.snap())
261	}
262
263	fn read(&self, version: u64)
264	-> Outcome<Vec<u8>>
265	{
266	let chain = res!(plan_at(&self.held, version));
267	self.follow(&chain)
268	}
269
270	fn follow(&self, chain: &[u64])
271	-> Outcome<Vec<u8>>
272	{
273	let kf = res!(self.file(chain[0]));
274	let mut patches: Vec<Vec<u8>> = Vec::new();
275	for n in &chain[1..] {
276	patches.push(res!(self.file(*n)));
277	}
278	materialise(kf, &patches)
279	}
280
281	fn file(&self, version: u64)
282	-> Outcome<Vec<u8>>
283	{
284	match self.bytes.get(&version) {
285	Some(b) => Ok(b.clone()),
286	None => Err(err!("Version {} has no file.", version; Missing, Data)),
287	}
288	}
289
290	fn stored(&self) -> usize {
291	self.bytes.values().map(\|b\| b.len()).sum()
292	}
293
294	fn keyframes(&self) -> usize {
295	self.held.iter().filter(\|(_, s)\| *s == Snap::Keyframe).count()
296	}
297	}
298
299	/// One turn's worth of change to a capp page, of the shapes the daimon's
300	/// own `file_edit` makes. Deterministic, so a failure is reproducible.
301	fn turn(page: &str, n: usize) -> String {
302	let mut lines: Vec<String> = page.split('\n').map(\|s\| s.to_string()).collect();
303	let len = lines.len();
304	match n % 4 {
305	// The commonest turn by far: one line, changed.
306	0 => {
307	let at = (n * 37 + 11) % len;
308	lines[at] = fmt!("{} <!-- {} -->", lines[at], n);
309	},
310	// A small block rewritten, which is what a fix to one function is.
311	1 => {
312	let at = (n * 53 + 7) % (len - 3);
313	for k in 0..3 {
314	lines[at + k] = fmt!(" /* turn {} line {} */", n, k);
315	}
316	},
317	// A section added, which is what a new lane or a new card is.
318	2 => {
319	let at = (n * 71 + 3) % len;
320	let mut block: Vec<String> = Vec::new();
321	block.push(fmt!("<section class=\"lane lane-{}\">", n));
322	for k in 0..6 {
323	block.push(fmt!(" <div class=\"row\" data-k=\"{}\">entry {}</div>", k, n));
324	}
325	block.push("</section>".to_string());
326	for (k, b) in block.into_iter().enumerate() {
327	lines.insert(at + k, b);
328	}
329	},
330	// A value changed in the stylesheet, which is a theme tweak.
331	_ => {
332	let at = (n * 17 + 5) % len;
333	lines[at] = lines[at].replace("128", &fmt!("{}", 100 + (n % 50)));
334	},
335	}
336	lines.join("\n")
337	}
338
339	/// A hundred turns of the real page, and the whole history read back.
340	fn hundred() -> Outcome<(Log, Vec<Vec<u8>>)> {
341	let mut log = Log::new();
342	let mut want: Vec<Vec<u8>> = Vec::new();
343	let mut cur = PAGE.to_string();
344	res!(log.write(0, cur.as_bytes()));
345	want.push(cur.clone().into_bytes());
346	for n in 1..=100usize {
347	cur = turn(&cur, n);
348	res!(log.write(n as u64, cur.as_bytes()));
349	want.push(cur.clone().into_bytes());
350	}
351	Ok((log, want))
352	}
353
354
355	/// The fixture is the file the measurements were taken against, so a page
356	/// swapped for a smaller one would quietly weaken every assertion below.
357	#[test]
358	fn test_the_fixture_is_the_real_shipped_capp_page() {
359	assert_eq!(PAGE.len(), 101_834, "the Log Life page is not the size it was measured at");
360	}
361
362	/// The whole claim. A hundred turns of the real page, every version
363	/// rebuilt from what was stored and compared with what was written.
364	#[test]
365	fn test_a_hundred_turns_of_the_real_capp_page_rebuild_byte_for_byte() -> Outcome<()> {
366	let (log, want) = res!(hundred());
367	for (n, w) in want.iter().enumerate() {
368	let got = res!(log.read(n as u64));
369	assert_eq!(
370	got.len(), w.len(),
371	"version {} rebuilt to {} bytes and was written as {}", n, got.len(), w.len());
372	assert!(got == *w, "version {} did not rebuild to the bytes it was written as", n);
373	}
374	Ok(())
375	}
376
377	/// What it costs, against what it cost. The old store wrote a full copy at
378	/// every version; a hundred turns of this page was 10.2 MB.
379	#[test]
380	fn test_a_hundred_turns_cost_a_fraction_of_a_hundred_copies() -> Outcome<()> {
381	let (log, want) = res!(hundred());
382	let full: usize = want.iter().map(\|w\| w.len()).sum();
383	let held = log.stored();
384	println!(
385	" {} versions of the {} byte Log Life page: {} bytes as a delta log, {} bytes as \
386	full copies, {:.0}x",
387	want.len(), PAGE.len(), held, full, full as f64 / held as f64);
388	assert!(
389	held * 6 < full,
390	"a hundred turns stored {} bytes against {} as full copies, which is not the \
391	saving this exists for", held, full);
392	// Five keyframes: version 0, then one every twenty after it.
393	assert_eq!(log.keyframes(), 6, "keyframe count over 101 versions");
394	Ok(())
395	}
396
397	/// The break the brief names. A reader that walked the chain but forgot
398	/// to apply the patches over it would return the keyframe, silently, and
399	/// look right in every test that only checks the call succeeded. Every
400	/// version between two keyframes must differ from the keyframe under it,
401	/// and must be its own bytes.
402	#[test]
403	fn test_no_version_is_ever_answered_with_the_keyframe_under_it() -> Outcome<()> {
404	let (log, want) = res!(hundred());
405	let mut checked = 0;
406	for n in 0..want.len() {
407	let chain = res!(plan_at(&log.held, n as u64));
408	let kf = res!(log.file(chain[0]));
409	let got = res!(log.read(n as u64));
410	assert!(got == want[n], "version {} is not its own bytes", n);
411	if chain.len() > 1 {
412	assert!(
413	got != kf,
414	"version {} came back as the keyframe at version {} under it",
415	n, chain[0]);
416	checked += 1;
417	}
418	}
419	assert!(checked >= 90, "only {} versions stood on a keyframe to be confused with", checked);
420	Ok(())
421	}
422
423	/// The interval is what bounds the blast radius and the history view's
424	/// reads, so the bound is asserted from both ends: never deeper than the
425	/// interval, and actually reaching it, so a keyframe on every version would
426	/// fail this rather than pass it.
427	#[test]
428	fn test_the_chain_is_never_deeper_than_the_keyframe_interval() -> Outcome<()> {
429	let (log, want) = res!(hundred());
430	let mut deepest = 0;
431	for n in 0..want.len() {
432	let chain = res!(plan_at(&log.held, n as u64));
433	assert!(
434	chain.len() <= KEYFRAME_EVERY,
435	"version {} is rebuilt from {} files, past the {} the interval allows",
436	n, chain.len(), KEYFRAME_EVERY);
437	deepest = deepest.max(chain.len());
438	}
439	assert_eq!(
440	deepest, KEYFRAME_EVERY,
441	"the deepest chain in a hundred versions was {} files, so the interval in force is \
442	not {}", deepest, KEYFRAME_EVERY);
443	Ok(())
444	}
445
446	/// A version with no snapshot of its own is not answered by the version
447	/// next to it. Answering "what did this hold at v12" with v9's bytes,
448	/// silently, is the failure a delta log must not have.
449	#[test]
450	fn test_a_version_with_no_snapshot_is_refused_rather_than_approximated() -> Outcome<()> {
451	let held = vec![
452	(0u64, Snap::Keyframe),
453	(1, Snap::Patch),
454	(2, Snap::Patch),
455	(4, Snap::Patch),
456	];
457	assert!(plan_at(&held, 3).is_err(), "version 3 was answered by one of its neighbours");
458	assert_eq!(res!(plan_at(&held, 2)), vec![0, 1, 2]);
459	// The page's reader is the one that MAY walk back, because a page is
460	// snapshotted only where it changed.
461	let (at, chain) = match res!(plan_upto(&held, 3)) {
462	Some(p) => p,
463	None => panic!("the page reader found nothing at or below version 3"),
464	};
465	assert_eq!(at, 2);
466	assert_eq!(chain, vec![0, 1, 2]);
467	Ok(())
468	}
469
470	/// A chain with a link missing is refused rather than half applied. The
471	/// patch after the gap was made against bytes that are not there, and it
472	/// says so.
473	#[test]
474	fn test_a_chain_with_a_link_missing_is_refused() -> Outcome<()> {
475	let (log, _want) = res!(hundred());
476	let chain = res!(plan_at(&log.held, 39));
477	assert!(chain.len() > 3);
478	let mut gapped = chain.clone();
479	gapped.remove(2);
480	assert!(
481	log.follow(&gapped).is_err(),
482	"a chain missing its third link rebuilt something anyway");
483	// And out of order, which is the same fault wearing a different hat.
484	let mut swapped = chain.clone();
485	swapped.swap(1, 2);
486	assert!(log.follow(&swapped).is_err(), "a chain applied out of order rebuilt something");
487	Ok(())
488	}
489
490	/// A patch recorded against one lineage cannot be applied inside another.
491	/// This is the fault that would otherwise be found months later: the
492	/// splices fit, the offsets are legal, and the answer is a file nobody
493	/// wrote.
494	#[test]
495	fn test_a_patch_from_another_lineage_is_refused() -> Outcome<()> {
496	let (mine, _) = res!(hundred());
497	// A second history from the same page but a different sequence of turns.
498	let mut theirs = Log::new();
499	let mut cur = PAGE.to_string();
500	res!(theirs.write(0, cur.as_bytes()));
501	for n in 1..=40usize {
502	cur = turn(&cur, n * 3 + 1);
503	res!(theirs.write(n as u64, cur.as_bytes()));
504	}
505	let chain = res!(plan_at(&mine.held, 25));
506	let kf = res!(mine.file(chain[0]));
507	let mut patches: Vec<Vec<u8>> = Vec::new();
508	for n in &chain[1..] {
509	patches.push(res!(mine.file(*n)));
510	}
511	// One patch swapped for the other history's patch at the same version.
512	let swap = patches.len() / 2;
513	patches[swap] = res!(theirs.file(chain[1 + swap]));
514	assert!(
515	materialise(kf, &patches).is_err(),
516	"a patch from another Diamond's history was applied without complaint");
517	Ok(())
518	}
519
520	/// The guarantee, stated as a property over content that has nothing in
521	/// common with the fixture: whatever [`record`] says is a patch, applying
522	/// it to the parent gives the new bytes exactly.
523	#[test]
524	fn test_nothing_is_recorded_as_a_patch_that_does_not_rebuild() -> Outcome<()> {
525	let long = PAGE.as_bytes().to_vec();
526	let mut binary: Vec<u8> = Vec::with_capacity(40_000);
527	let mut x: u64 = 0x2545_f491_4f6c_dd1d;
528	for _ in 0..40_000 {
529	x ^= x << 13; x ^= x >> 7; x ^= x << 17;
530	binary.push((x & 0xff) as u8);
531	}
532	let mut shuffled = binary.clone();
533	shuffled[100..200].fill(0);
534	shuffled.extend_from_slice(b"tail");
535	let turned = turn(PAGE, 7);
536	let cases: Vec<(&[u8], &[u8])> = vec![
537	(b"", b""),
538	(b"", &long),
539	(&long, b""),
540	(&long, &long),
541	(&long, b"a completely different page"),
542	(b"a completely different page", &long),
543	(&binary, &shuffled),
544	(&shuffled, &binary),
545	(&long, turned.as_bytes()),
546	];
547	// A pool of snapshots that is not due a keyframe, so `record` is free
548	// to choose a patch and the choice is the thing under test.
549	let held = vec![(0u64, Snap::Keyframe), (1, Snap::Patch)];
550	let mut patched = 0;
551	for (old, new) in cases {
552	match record(Some(old), new, &held) {
553	Recorded::Keyframe(b) => assert_eq!(b, new.to_vec(), "a keyframe is the file"),
554	Recorded::Patch(p) => {
555	patched += 1;
556	let back = res!(diff::apply_patch(old, &p));
557	assert!(back == new.to_vec(), "a recorded patch did not rebuild its version");
558	assert!(p.len() < new.len(), "a patch was stored that is not smaller");
559	},
560	}
561	}
562	assert!(patched >= 3, "only {} of the cases were stored as patches", patched);
563	Ok(())
564	}
565
566	/// The worst case measured against this page -- a pasted section of sixty
567	/// rows -- still costs a fraction of a full copy.
568	#[test]
569	fn test_a_pasted_section_still_costs_less_than_the_page() -> Outcome<()> {
570	let mut lines: Vec<String> = PAGE.split('\n').map(\|s\| s.to_string()).collect();
571	let at = lines.len() / 2;
572	for k in 0..60 {
573	lines.insert(at + k, fmt!(
574	" <div class=\"row\" data-k=\"{}\"><span>meal</span><span>{} kcal</span></div>",
575	k, 300 + k * 7));
576	}
577	let new = lines.join("\n");
578	let patch = res!(diff::make_patch(PAGE.as_bytes(), new.as_bytes()));
579	assert!(
580	patch.len() * 5 < PAGE.len(),
581	"sixty pasted rows cost {} bytes against a page of {}", patch.len(), PAGE.len());
582	assert!(res!(diff::apply_patch(PAGE.as_bytes(), &patch)) == new.as_bytes().to_vec());
583	Ok(())
584	}
585
586	/// Where the splices would cost more than the file, the file is stored.
587	#[test]
588	fn test_a_wholesale_replacement_is_stored_as_the_file() -> Outcome<()> {
589	let held = vec![(0u64, Snap::Keyframe), (1, Snap::Patch)];
590	// Two files with nothing in common and nothing to save.
591	let rec = record(Some(b"aaaa"), b"zzzz", &held);
592	assert!(!rec.is_patch(), "four bytes were stored as splices over four bytes");
593	assert_eq!(rec.bytes(), b"zzzz");
594	Ok(())
595	}
596
597	/// Migration. Every Diamond in the wild holds a full copy at every
598	/// version, and a full copy is exactly what a keyframe is -- so nothing is
599	/// converted, nothing is rewritten, and the first version written after the
600	/// upgrade is a patch against the last full copy.
601	#[test]
602	fn test_an_existing_diamond_of_full_copies_needs_no_conversion() -> Outcome<()> {
603	let mut log = Log::new();
604	// A Diamond that has been running since before this module existed.
605	let mut cur = PAGE.to_string();
606	for n in 0..=137u64 {
607	if n > 0 {
608	cur = turn(&cur, n as usize);
609	}
610	log.bytes.insert(n, cur.clone().into_bytes());
611	log.held.push((n, Snap::Keyframe));
612	}
613	// Every one of them still reads, with no chain to walk.
614	for n in [0u64, 1, 68, 137] {
615	assert_eq!(res!(plan_at(&log.held, n)), vec![n], "version {} needs a chain", n);
616	assert!(res!(log.read(n)).len() > 90_000);
617	}
618	// And the next version is a patch, not a copy.
619	let next = turn(&cur, 138);
620	let snap = res!(log.write(138, next.as_bytes()));
621	assert_eq!(snap, Snap::Patch, "the first version after the upgrade was a full copy");
622	assert!(res!(log.read(138)) == next.as_bytes().to_vec());
623	Ok(())
624	}
625
626	/// The page is snapshotted only where it changed, so its versions are
627	/// sparse and its keyframes are counted over the snapshots rather than
628	/// taken from the version number.
629	#[test]
630	fn test_the_page_keyframes_are_counted_over_its_own_sparse_versions() -> Outcome<()> {
631	let mut log = Log::new();
632	let mut cur = PAGE.to_string();
633	// Version numbers a page edit might land on across a busy Diamond.
634	let at: Vec<u64> = (0..60u64).map(\|k\| k * k + k).collect();
635	for (i, n) in at.iter().enumerate() {
636	if i > 0 {
637	cur = turn(&cur, i);
638	}
639	res!(log.write(*n, cur.as_bytes()));
640	}
641	// One in twenty is a full copy, whatever the numbers were.
642	assert_eq!(log.keyframes(), 3, "keyframes over 60 sparse page snapshots");
643	// And a version between two page snapshots reads as the one before it.
644	let between = at[7] + 1;
645	let (target, _chain) = match res!(plan_upto(&log.held, between)) {
646	Some(p) => p,
647	None => panic!("no page at or below version {}", between),
648	};
649	assert_eq!(target, at[7]);
650	Ok(())
651	}
652
653	/// A history built entirely of patches, with no full copy under it, is
654	/// refused. It cannot arise from [`record`], which writes a keyframe
655	/// wherever there is nothing to build on, and it is what a lost keyframe
656	/// leaves behind.
657	#[test]
658	fn test_a_history_with_no_full_copy_under_it_is_refused() {
659	let held = vec![(0u64, Snap::Patch), (1, Snap::Patch)];
660	assert!(plan_at(&held, 1).is_err(), "a history of patches alone was planned");
661	assert!(plan_upto(&held, 9).is_err(), "a history of patches alone was planned");
662	assert!(wants_keyframe(&held), "a history with no full copy is not asking for one");
663	}
664
665	/// A patch has to survive the pack a sync carries it in. A version
666	/// snapshot used to be text in every case, and a patch is not: its header
667	/// carries two checksums, which are arbitrary bytes, so most patches are not
668	/// valid UTF-8 and travel base64 in the pack's `binary` map instead of as
669	/// themselves. That map is not new, but nothing routine had ever gone
670	/// through it -- a Diamond carrying a picture did -- so the path a hundred
671	/// versions of every Diamond now take was, until this, exercised only by
672	/// what somebody happened to drag in.
673	#[test]
674	fn test_a_patch_survives_the_pack_a_sync_carries_it_in() -> Outcome<()> {
675	let (log, _want) = res!(hundred());
676	let mut files: Vec<(String, Vec<u8>)> = Vec::new();
677	for (n, snap) in &log.held {
678	let ext = match snap {
679	Snap::Keyframe => ".html",
680	Snap::Patch => ".hpatch",
681	};
682	files.push((fmt!("versions/{:04}{}", n, ext), res!(log.file(*n))));
683	}
684	let packed = crate::protocol::pack_diamond("abc123", 1, &files);
685	let mut binary = 0;
686	let mut text = 0;
687	for (path, bytes) in &files {
688	// The pack's own rule for which map a file goes in.
689	if std::str::from_utf8(bytes).is_ok() {
690	// Valid UTF-8 travels as itself, and JSON is lossless over it.
691	text += 1;
692	continue;
693	}
694	let raw = res!(crate::llm::extract_json_string(&packed, path)
695	.ok_or_else(\|\| err!("'{}' is in neither of the pack's maps.", path; Missing)));
696	let got = res!(crate::protocol::unpack_binary(path, &raw));
697	assert!(got == *bytes, "'{}' did not survive the pack", path);
698	binary += 1;
699	}
700	assert!(binary > 50, "only {} of {} patches took the binary path", binary, files.len());
701	assert!(text > 0, "no snapshot at all travelled as text");
702	Ok(())
703	}
704
705	/// The interval in force, read straight off the counting rule rather than
706	/// through a hundred turns of a real page.
707	#[test]
708	fn test_a_keyframe_is_due_once_the_interval_is_used_up() {
709	let mut held = vec![(0u64, Snap::Keyframe)];
710	for k in 1..KEYFRAME_EVERY {
711	assert!(
712	!wants_keyframe(&held),
713	"a keyframe was called for with {} patches over the last one", k - 1);
714	held.push((k as u64, Snap::Patch));
715	}
716	assert!(
717	wants_keyframe(&held),
718	"{} patches stand over the last full copy and none is due",
719	KEYFRAME_EVERY - 1);
720	assert!(wants_keyframe(&[]), "an empty history is not asking for a full copy");
721	}
722	}