oxedyne/fe2o3 — fe2o3_ore/src/seq/file

oxedyne/fe2o3/fe2o3_ore/src/seq/file_tests.rs

59.2 KiB, 100 runs

created by r1870400018:18956, 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	//! The file-identity cases: what happens when content crosses a file boundary,
2	//! when two branches create one path, and when a file is deleted around a move.
3	//!
4	//! Every case here was written and predicted in the throwaway multi-file oracle
5	//! before it was run, and every expectation below is that oracle's answer under
6	//! the rule this crate now implements: content operations carry no file, a file's
7	//! creation mints an origin anchor, and a file is the subtree beneath one.
8	//!
9	//! Two invariants are checked in every case, over the whole repository rather
10	//! than one file. No byte may render in two places at once, which is what a
11	//! per-file claim register produces and what no per-file check would see. And no
12	//! live byte may render nowhere. Both are the point of the exercise; the bytes
13	//! themselves are only how the answer is read.
14	//!
15	//! The ten single-file cases are beside this file in `tests.rs`, and they run
16	//! through this same engine: file identity must not perturb single-file
17	//! semantics, and that they are unchanged is the instrument for saying so.
18	//!
19	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
20	//! Anthropic Claude
21
22	use crate::id::{
23	Anchor,
24	ContentId,
25	ContentRange,
26	OpId,
27	ReplicaId,
28	};
29	use crate::op::{
30	Header,
31	Mode,
32	Op,
33	};
34	use crate::seq::render::{
35	Flag,
36	Rendered,
37	Repo,
38	Span,
39	};
40	use crate::seq::{
41	OpOrder,
42	Sequence,
43	};
44
45	use oxedyne_fe2o3_core::prelude::*;
46
47
48	// The shopping list of the published worked case.
49	const LIST: &[u8] = b"- Eggs\n- Milk\n- Cheese\n";
50
51
52	/// One replica of a repository of several files: the frontend that turns
53	/// index-based editing intent, in a named file, into content-anchored
54	/// operations.
55	///
56	/// Nothing here distinguishes a move within a file from a move between two,
57	/// except which render the destination gap is read from. That is the claim the
58	/// whole exercise was to test, stated as code.
59	struct Replica {
60	id: u64, // every operation of this replica is named by it
61	seq: Sequence,
62	}
63
64	impl Replica {
65
66	fn new(id: u64) -> Self {
67	Self { id, seq: Sequence::new() }
68	}
69
70	/// A Lamport counter, and everything this replica can see as the operation's
71	/// parents.
72	fn next_head(&self)
73	-> Outcome<Header>
74	{
75	let seen = self.seq.iter().map(\|(id, _)\| id.counter).max().unwrap_or(0);
76	Header::new(
77	OpId::new(ReplicaId::new(self.id), seen + 1),
78	self.seq.causality().heads(),
79	)
80	}
81
82	fn recv(&mut self, op: (Header, Op))
83	-> Outcome<()>
84	{
85	self.seq.apply(op.0, op.1)
86	}
87
88	fn view(&self, file: OpId)
89	-> Outcome<Rendered>
90	{
91	let repo = res!(self.seq.render());
92	match repo.file(file) {
93	Some(f) => Ok(f.clone()),
94	None => Err(err!("The replica has no file {}.", file; Test, Missing)),
95	}
96	}
97
98	fn author(&mut self, op: Op)
99	-> Outcome<(Header, Op)>
100	{
101	let head = res!(self.next_head());
102	res!(self.seq.apply(head.clone(), op.clone()));
103	Ok((head, op))
104	}
105
106	fn create(&mut self, path: &[u8])
107	-> Outcome<((Header, Op), OpId)>
108	{
109	let made = res!(self.author(Op::FileCreate { path: path.to_vec() }));
110	let id = made.0.id();
111	Ok((made, id))
112	}
113
114	fn rename(&mut self, file: OpId, path: &[u8])
115	-> Outcome<(Header, Op)>
116	{
117	self.author(Op::FileRename { file, path: path.to_vec() })
118	}
119
120	fn remove(&mut self, file: OpId)
121	-> Outcome<(Header, Op)>
122	{
123	self.author(Op::FileDelete { file })
124	}
125
126	fn set_mode(&mut self, file: OpId, mode: Mode)
127	-> Outcome<(Header, Op)>
128	{
129	self.author(Op::FileMode { file, mode })
130	}
131
132	fn insert(&mut self, file: OpId, at: usize, bytes: &[u8])
133	-> Outcome<(Header, Op)>
134	{
135	let op = res!(res!(self.view(file)).splice(at, 0, bytes.to_vec()));
136	self.author(op)
137	}
138
139	fn delete(&mut self, file: OpId, at: usize, len: usize)
140	-> Outcome<(Header, Op)>
141	{
142	let op = res!(res!(self.view(file)).splice(at, len, Vec::new()));
143	self.author(op)
144	}
145
146	/// One splice, not a deletion and an insertion.
147	fn replace(&mut self, file: OpId, at: usize, len: usize, bytes: &[u8])
148	-> Outcome<(Header, Op)>
149	{
150	let op = res!(res!(self.view(file)).splice(at, len, bytes.to_vec()));
151	self.author(op)
152	}
153
154	/// At an index of each file.
155	fn move_across(
156	&mut self,
157	from: OpId,
158	at: usize,
159	len: usize,
160	to: OpId,
161	dest: usize,
162	)
163	-> Outcome<(Header, Op)>
164	{
165	let src = res!(self.view(from));
166	let dst = res!(self.view(to));
167	let op = res!(src.move_into(at, len, &dst, dest));
168	self.author(op)
169	}
170
171	fn note(&mut self, file: OpId, at: usize, len: usize, text: &[u8])
172	-> Outcome<(Header, Op)>
173	{
174	let op = res!(res!(self.view(file)).note_on(at, len, text.to_vec()));
175	self.author(op)
176	}
177	}
178
179
180	/// Creates the named files with the given contents on replica zero, then hands
181	/// out `n` further replicas that have seen all of it.
182	fn stage(files: &[(&[u8], &[u8])], n: u64)
183	-> Outcome<(Vec<Replica>, Vec<(Header, Op)>, Vec<OpId>)>
184	{
185	let mut origin = Replica::new(0);
186	let mut ops: Vec<(Header, Op)> = Vec::new();
187	let mut ids: Vec<OpId> = Vec::new();
188	for (path, text) in files {
189	let (made, id) = res!(origin.create(path));
190	ops.push(made);
191	ids.push(id);
192	if !text.is_empty() {
193	ops.push(res!(origin.insert(id, 0, text)));
194	}
195	}
196	let mut reps: Vec<Replica> = Vec::new();
197	for i in 1..=n {
198	let mut r = Replica::new(i);
199	for op in &ops {
200	res!(r.recv(op.clone()));
201	}
202	reps.push(r);
203	}
204	Ok((reps, ops, ids))
205	}
206
207	fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
208	if k == idx.len() {
209	out.push(idx.clone());
210	return;
211	}
212	for i in k..idx.len() {
213	idx.swap(k, i);
214	permute(idx, k + 1, out);
215	idx.swap(k, i);
216	}
217	}
218
219	/// A one-line listing of the live files, as a working copy would show them.
220	fn listing(repo: &Repo) -> String {
221	let mut files: Vec<&Rendered> = repo.files().iter().filter(\|f\| f.is_live()).collect();
222	files.sort_by_key(\|f\| (f.path().to_vec(), OpOrder::of(&f.file())));
223	let mut s = String::new();
224	for f in files {
225	// A mode is shown only where it is not the one a file has by default, so
226	// that every case written before the vocabulary had modes reads as it did
227	// -- and every one of them now proves, for nothing, that the mode is a
228	// function of the operation set and not of the delivery order.
229	let mode = if f.mode().is_normal() {
230	String::new()
231	} else {
232	fmt!("[{}]", f.mode())
233	};
234	s.push_str(&fmt!("{}{}={:?} ", f.path_lossy(), mode, f.text_lossy()));
235	}
236	s.trim_end().to_string()
237	}
238
239	/// Applies an operation set in every delivery order where the set is small
240	/// enough, or in every rotation and a spread of shuffles where it is not, and
241	/// requires that all of them render the same files and raise the same flags.
242	///
243	/// Conservation is checked repository-wide on every order: nothing rendered
244	/// twice, nothing live rendered nowhere.
245	fn converge(ops: &[(Header, Op)])
246	-> Outcome<Repo>
247	{
248	let n = ops.len();
249	let mut orders: Vec<Vec<usize>> = Vec::new();
250	if n <= 7 {
251	let mut idx: Vec<usize> = (0..n).collect();
252	permute(&mut idx, 0, &mut orders);
253	} else {
254	// Every rotation, the reverse, and a spread of shuffles, since
255	// enumerating factorially many orders buys nothing over sampling them.
256	for k in 0..n {
257	orders.push((0..n).map(\|i\| (i + k) % n).collect());
258	}
259	orders.push((0..n).rev().collect());
260	let mut state = 0x0f1e_2d3c_4b5a_6978u64.wrapping_add(n as u64);
261	let mut next = move \|\| {
262	state = state
263	.wrapping_mul(6_364_136_223_846_793_005)
264	.wrapping_add(1_442_695_040_888_963_407);
265	(state >> 33) as usize
266	};
267	for _ in 0..200 {
268	let mut idx: Vec<usize> = (0..n).collect();
269	for i in (1..idx.len()).rev() {
270	idx.swap(i, next() % (i + 1));
271	}
272	orders.push(idx);
273	}
274	}
275	let mut first: Option<Repo> = None;
276	for order in &orders {
277	let mut seq = Sequence::new();
278	for i in order {
279	res!(seq.apply(ops[i].0.clone(), ops[i].1.clone()));
280	}
281	let got = res!(seq.render());
282	res!(seq.check_conservation(&got));
283	assert_eq!(got.stats().orphaned, 0, "a slot belonged to no file");
284	match &first {
285	None => first = Some(got),
286	Some(want) => {
287	if listing(want) != listing(&got) {
288	return Err(err!(
289	"Delivery order changed the render: {} against {}.",
290	listing(want), listing(&got);
291	Test, Mismatch));
292	}
293	if want.flags() != got.flags() {
294	return Err(err!(
295	"Delivery order changed the flags: {:?} against {:?}.",
296	want.flags(), got.flags();
297	Test, Mismatch));
298	}
299	// A note is derived from the render, so this ought to come for
300	// nothing; it is asserted anyway, in every case, because "ought to"
301	// is not a test.
302	if want.notes() != got.notes() {
303	return Err(err!(
304	"Delivery order changed the notes: {:?} against {:?}.",
305	want.notes(), got.notes();
306	Test, Mismatch));
307	}
308	for (a, b) in want.files().iter().zip(got.files()) {
309	if a.notes() != b.notes() {
310	return Err(err!(
311	"Delivery order changed the notes of the file {}: {:?} \
312	against {:?}.", a.file(), a.notes(), b.notes();
313	Test, Mismatch));
314	}
315	}
316	},
317	}
318	}
319	match first {
320	Some(r) => Ok(r),
321	None => Err(err!("No delivery order was tried."; Test, Bug)),
322	}
323	}
324
325	/// Runs an operation set under every delivery order and checks the live files
326	/// against the answer the case prescribes.
327	fn case(expect: &str, ops: &[(Header, Op)])
328	-> Outcome<Repo>
329	{
330	let repo = res!(converge(ops));
331	assert_eq!(listing(&repo), expect);
332	Ok(repo)
333	}
334
335	/// The text of one file, deleted or not.
336	fn text(repo: &Repo, file: OpId)
337	-> Outcome<String>
338	{
339	match repo.file(file) {
340	Some(f) => Ok(f.text_lossy()),
341	None => Err(err!("The repository has no file {}.", file; Test, Missing)),
342	}
343	}
344
345
346	// ┌───────────────────────────────────────────────────────────────────────────┐
347	// │ THE FILE-IDENTITY CASES │
348	// └───────────────────────────────────────────────────────────────────────────┘
349
350	/// The headline claim: a concurrent edit inside a range that moves *between
351	/// files* follows it, for exactly the reason an in-file one does.
352	///
353	/// This is the case that decided the design. Where a content operation records a
354	/// file, the edit's anchor names content that has left that file and cannot
355	/// follow it out, so the insertion stays behind and the word is torn in half
356	/// across two files -- `Soy m` in one and `ilk` in the other, everything
357	/// converging and nothing lost, which is a placement failure of the kind a user
358	/// would call corruption. Naming no file at all is what makes the edit arrive.
359	#[test]
360	fn a_cross_file_move_carries_a_concurrent_edit_with_it() -> Outcome<()> {
361	let (mut reps, mut ops, ids) = res!(stage(
362	&[(b"a.txt", LIST), (b"b.txt", b"HEADER\n")], 2));
363	let (a, b) = (ids[0], ids[1]);
364	let (r1, r2) = reps.split_at_mut(1);
365	// Replica 1 moves "- Milk\n" out of a.txt and onto the end of b.txt.
366	ops.push(res!(r1[0].move_across(a, 7, 7, b, 7)));
367	// Replica 2 concurrently turns "Milk" into "Soy milk", in a.txt.
368	ops.push(res!(r2[0].replace(a, 9, 1, b"Soy m")));
369	res!(case(
370	"a.txt=\"- Eggs\\n- Cheese\\n\" b.txt=\"HEADER\\n- Soy milk\\n\"",
371	&ops,
372	));
373	Ok(())
374	}
375
376	#[test]
377	fn a_cross_file_move_arbitrates_against_an_edit_at_its_destination() -> Outcome<()> {
378	let (mut reps, mut ops, ids) = res!(stage(
379	&[(b"a.txt", LIST), (b"b.txt", b"HEADER\n")], 2));
380	let (a, b) = (ids[0], ids[1]);
381	let (r1, r2) = reps.split_at_mut(1);
382	// Replica 1 moves "- Milk\n" to the start of b.txt.
383	ops.push(res!(r1[0].move_across(a, 7, 7, b, 0)));
384	// Replica 2 concurrently types an X at the start of b.txt.
385	ops.push(res!(r2[0].insert(b, 0, b"X")));
386	res!(case(
387	"a.txt=\"- Eggs\\n- Cheese\\n\" b.txt=\"- Milk\\nXHEADER\\n\"",
388	&ops,
389	));
390	Ok(())
391	}
392
393	/// A walk that reconstructs the association from a path decides this by arrival
394	/// order: the later creation takes the path, and the earlier file keeps its
395	/// operations and its bytes and renders nowhere. Under identity both files exist,
396	/// both keep their bytes, and the collision is a naming question at
397	/// materialisation time rather than a silent loss.
398	#[test]
399	fn two_branches_creating_one_path_make_two_files() -> Outcome<()> {
400	let mut r1 = Replica::new(1);
401	let mut r2 = Replica::new(2);
402	let (c1, f1) = res!(r1.create(b"notes.md"));
403	let s1 = res!(r1.insert(f1, 0, b"one"));
404	let (c2, f2) = res!(r2.create(b"notes.md"));
405	let s2 = res!(r2.insert(f2, 0, b"two"));
406	let repo = res!(converge(&[c1, s1, c2, s2]));
407	assert_eq!(res!(text(&repo, f1)), "one");
408	assert_eq!(res!(text(&repo, f2)), "two");
409	// Both are live and both claim the path, which the repository reports rather
410	// than resolving: which one a working copy writes there is a policy, and the
411	// higher in op order keeping the name is one answer among several.
412	let clashes = repo.clashes();
413	assert_eq!(clashes.len(), 1);
414	assert_eq!(clashes[0].0, b"notes.md");
415	assert_eq!(repo.at_path(b"notes.md").len(), 2);
416	assert!(OpOrder::of(&f2) > OpOrder::of(&f1),
417	"the later creation is higher in op order");
418	Ok(())
419	}
420
421	/// A file deleted just after content moved out of it. The bytes that left must
422	/// survive; the bytes that stayed must not render anywhere a reader looks.
423	///
424	/// This is the working form of the second cost: a file's deletion retires a file
425	/// and destroys no atom.
426	#[test]
427	fn deleting_a_file_keeps_what_moved_out_of_it() -> Outcome<()> {
428	let (mut reps, mut ops, ids) = res!(stage(
429	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 1));
430	let (a, b) = (ids[0], ids[1]);
431	ops.push(res!(reps[0].move_across(a, 5, 5, b, 0)));
432	ops.push(res!(reps[0].remove(a)));
433	let repo = res!(case("b.txt=\"move\\n\"", &ops));
434	assert_eq!(res!(text(&repo, b)), "move\n");
435	// What stayed behind is held rather than destroyed: the deleted file still
436	// holds it, and the render says how much is withheld.
437	assert_eq!(res!(text(&repo, a)), "keep\n");
438	assert_eq!(repo.stats().withheld, 5);
439	Ok(())
440	}
441
442	/// The same, with the deletion expressed the way it must not be: as a splice
443	/// removing everything the file held.
444	///
445	/// A tombstone is repository-global and follows the content, so a deletion that
446	/// kills bytes rather than retiring a file destroys what has just moved out of
447	/// it. That is why file lifecycle and content lifecycle are separate operations,
448	/// and this is the cost stated as a test.
449	#[test]
450	fn a_content_delete_destroys_what_moved_out() -> Outcome<()> {
451	let (mut reps, mut ops, ids) = res!(stage(
452	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
453	let (a, b) = (ids[0], ids[1]);
454	let (r1, r2) = reps.split_at_mut(1);
455	ops.push(res!(r1[0].move_across(a, 5, 5, b, 0)));
456	// Replica 2 empties a.txt by content, concurrently.
457	ops.push(res!(r2[0].delete(a, 0, 10)));
458	res!(case("a.txt=\"\" b.txt=\"\"", &ops));
459	Ok(())
460	}
461
462	/// Two agents reorganising two files at once, each moving one file's contents
463	/// into the other: a genuine cycle in the anchor graph, across a file boundary.
464	///
465	/// The cycle is arbitrated rather than demoted. Both moves are treated as one
466	/// concurrent group, the higher in op order wins wholly, and the other is confined
467	/// -- its content stays where it was, and both files are told.
468	///
469	/// b.txt is empty because its author emptied it, having moved the whole of it
470	/// into a.txt, and that move completed. The string alone looks like the collapse
471	/// this rule exists to prevent, and it is the opposite of it: under demotion a.txt
472	/// was emptied by the renderer, which nobody asked for.
473	#[test]
474	fn a_cross_file_cycle_lets_the_later_move_win() -> Outcome<()> {
475	let (mut reps, mut ops, ids) = res!(stage(
476	&[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n")], 2));
477	let (a, b) = (ids[0], ids[1]);
478	let (r1, r2) = reps.split_at_mut(1);
479	// Replica 1 moves the whole of a.txt into b.txt, after its first byte.
480	let m1 = res!(r1[0].move_across(a, 0, 4, b, 1));
481	let m1_id = m1.0.id();
482	ops.push(m1);
483	// Replica 2 concurrently moves the whole of b.txt into a.txt, after its
484	// first byte.
485	let m2 = res!(r2[0].move_across(b, 0, 4, a, 1));
486	let m2_id = m2.0.id();
487	ops.push(m2);
488	assert!(OpOrder::of(&m2_id) > OpOrder::of(&m1_id), "the second move is higher");
489	let repo = res!(case("a.txt=\"axyz\\nbc\\n\" b.txt=\"\"", &ops));
490	assert_eq!(res!(text(&repo, b)), "");
491	// The lower move did not happen: its block is still in a.txt, and b.txt is the
492	// file it was aimed at and did not reach.
493	assert!(repo.flags().contains(&Flag::Confined { op: m1_id, home: a, denied: b }),
494	"flags were {:?}", repo.flags());
495	assert!(repo.flags().contains(&Flag::Won { op: m2_id }),
496	"flags were {:?}", repo.flags());
497	// Nothing was demoted, so nothing crossed a boundary by demotion either.
498	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Demoted { .. })),
499	"a cross-file cycle reached demotion: {:?}", repo.flags());
500	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::CrossedFile { .. })),
501	"flags were {:?}", repo.flags());
502	// Both files are told, since the flag is about the pair of them.
503	for file in [a, b] {
504	match repo.file(file) {
505	Some(f) => assert!(
506	f.flags().iter().any(\|g\| matches!(g, Flag::Confined { .. })),
507	"the file {} was not told", file),
508	None => return Err(err!("A file went missing."; Test, Missing)),
509	}
510	}
511	Ok(())
512	}
513
514	/// The same two-file cycle, with a third replica editing inside one of the
515	/// cycling blocks.
516	///
517	/// The composition question the arbitration has to answer. The edit's origin names
518	/// content, the content is owned by whoever owns it after the arbitration, and the
519	/// edit binds there without anything being written to make it do so.
520	#[test]
521	fn an_edit_inside_a_cycling_block_follows_the_block() -> Outcome<()> {
522	let (mut reps, mut ops, ids) = res!(stage(
523	&[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n")], 3));
524	let (a, b) = (ids[0], ids[1]);
525	ops.push(res!(reps[0].move_across(a, 0, 4, b, 1)));
526	ops.push(res!(reps[1].move_across(b, 0, 4, a, 1)));
527	// Concurrently with both, an exclamation mark between 'b' and 'c'.
528	ops.push(res!(reps[2].insert(a, 2, b"!")));
529	let repo = res!(case("a.txt=\"axyz\\nb!c\\n\" b.txt=\"\"", &ops));
530	assert!(res!(text(&repo, a)).contains("b!c"), "the edit went astray");
531	Ok(())
532	}
533
534	/// A cycle of three whose middle member never leaves its file, which is what
535	/// whole-cycle arbitration costs.
536	///
537	/// A two-cycle cannot be mixed -- each member lands inside the other's source, so
538	/// either both cross a boundary or neither does -- and three is the shortest cycle
539	/// that can hold an in-file move. **That in-file move is voided along with the
540	/// rest**, though it never went near a file boundary and was in the cycle only by
541	/// accident of what it anchored to. It is the strongest argument against the rule,
542	/// and the answer is that a voided move is flagged as not having happened whereas
543	/// a misplaced one has to be found: under demotion this same move is carried into
544	/// a file its author never named.
545	#[test]
546	fn a_mixed_cycle_voids_its_in_file_member_too() -> Outcome<()> {
547	let (mut reps, mut ops, ids) = res!(stage(
548	&[(b"a.txt", b"abc\n"), (b"b.txt", b"wxyz")], 3));
549	let (a, b) = (ids[0], ids[1]);
550	// The whole of a.txt into b.txt, after 'w': crossing.
551	let m1 = res!(reps[0].move_across(a, 0, 4, b, 1));
552	let m1_id = m1.0.id();
553	ops.push(m1);
554	// "wx" to after 'y', within b.txt: not crossing anything.
555	let m2 = res!(reps[1].move_across(b, 0, 2, b, 3));
556	let m2_id = m2.0.id();
557	ops.push(m2);
558	// "yz" out of b.txt into a.txt, after 'a': crossing back.
559	let m3 = res!(reps[2].move_across(b, 2, 2, a, 1));
560	let m3_id = m3.0.id();
561	ops.push(m3);
562	let repo = res!(case("a.txt=\"ayzbc\\n\" b.txt=\"wx\"", &ops));
563	assert!(repo.flags().contains(&Flag::Won { op: m3_id }),
564	"flags were {:?}", repo.flags());
565	assert!(repo.flags().contains(&Flag::Confined { op: m1_id, home: a, denied: b }),
566	"flags were {:?}", repo.flags());
567	// The in-file move is confined with one file at both ends, which is the honest
568	// way to say that it was voided for being in the cycle and nothing else.
569	assert!(repo.flags().contains(&Flag::Confined { op: m2_id, home: b, denied: b }),
570	"flags were {:?}", repo.flags());
571	Ok(())
572	}
573
574	/// An author re-moving their own block, having seen the move that raced it.
575	///
576	/// The first move is superseded and owns nothing, so it leaves the anchor graph;
577	/// the cycle is between the concurrent move and the re-move. The re-move wins, as
578	/// the op-order maximum and as the informed member both, and a block whose author
579	/// twice said "into b.txt" renders in b.txt.
580	///
581	/// This is also the case that makes the birth classifier necessary. Voiding the
582	/// whole cycle to ask which files it runs between resurrects the superseded move,
583	/// which carries the content over the boundary itself, and the cycle then looks as
584	/// though it stays inside one file. Asking where the bytes were written is what
585	/// sees through it.
586	#[test]
587	fn an_informed_re_move_wins_its_cycle() -> Outcome<()> {
588	let (mut reps, mut ops, ids) = res!(stage(
589	&[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n")], 2));
590	let (a, b) = (ids[0], ids[1]);
591	// The splices that wrote the two files' contents.
592	let (sa, sb) = (ops[1].0.id(), ops[3].0.id());
593	let (r1, r2) = reps.split_at_mut(1);
594	ops.push(res!(r1[0].move_across(a, 0, 4, b, 1)));
595	let m2 = res!(r2[0].move_across(b, 0, 4, a, 1));
596	let m2_id = m2.0.id();
597	ops.push(m2.clone());
598	// Replica 1 receives the move that raced it, and moves its own block again, to
599	// the end of what b.txt originally held.
600	res!(r1[0].recv(m2));
601	let m3 = res!(r1[0].author(Op::Move {
602	src: vec![res!(ContentRange::new(sa, 0, 4))],
603	left: Some(Anchor::after(ContentId::new(sb, 3))),
604	right: None,
605	}));
606	let m3_id = m3.0.id();
607	ops.push(m3);
608	let repo = res!(case("a.txt=\"\" b.txt=\"xyz\\nabc\\n\"", &ops));
609	assert!(repo.flags().contains(&Flag::Won { op: m3_id }),
610	"flags were {:?}", repo.flags());
611	// The confined move's own content stays in b.txt, which is what matters to its
612	// author. The file it is reported as having been denied is b.txt as well, and
613	// that is an artefact of the counterfactual worth stating rather than hiding:
614	// the file a destination anchor is in is read off a layout with the cycle
615	// voided, and voiding this cycle resurrects the superseded first move, which
616	// carries the anchor into b.txt itself. The classification is still right,
617	// because the birth reading sees the boundary the counterfactual has hidden.
618	assert!(repo.flags().contains(&Flag::Confined { op: m2_id, home: b, denied: b }),
619	"flags were {:?}", repo.flags());
620	Ok(())
621	}
622
623	#[test]
624	fn a_move_out_of_a_file_survives_its_deletion() -> Outcome<()> {
625	let (mut reps, mut ops, ids) = res!(stage(
626	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
627	let (a, b) = (ids[0], ids[1]);
628	let (r1, r2) = reps.split_at_mut(1);
629	ops.push(res!(r1[0].move_across(a, 5, 5, b, 0)));
630	ops.push(res!(r2[0].remove(a)));
631	let repo = res!(case("b.txt=\"move\\n\"", &ops));
632	assert_eq!(res!(text(&repo, b)), "move\n");
633	Ok(())
634	}
635
636	/// Neither is difficult now, and the case is here because the vocabulary this
637	/// replaces could not do it at all: a splice that names no existing content
638	/// could only be routed by the path it recorded, and the rename had just made
639	/// that path wrong. The splice names the file's origin anchor instead, and a
640	/// rename cannot touch an identity.
641	#[test]
642	fn an_insertion_survives_the_rename_of_its_file() -> Outcome<()> {
643	let (mut reps, mut ops, ids) = res!(stage(&[(b"a.txt", b"")], 2));
644	let a = ids[0];
645	let (r1, r2) = reps.split_at_mut(1);
646	ops.push(res!(r1[0].rename(a, b"b.txt")));
647	ops.push(res!(r2[0].insert(a, 0, b"hi")));
648	res!(case("b.txt=\"hi\"", &ops));
649	Ok(())
650	}
651
652	/// Three agents reorganising three files at once, each emptying one into the
653	/// next: the cycle at length three, and across files.
654	///
655	/// One move completes and two are confined, so two of the three files keep their
656	/// own content. c.txt is empty because its author emptied it into a.txt, which is
657	/// the move that won.
658	#[test]
659	fn a_three_file_cycle_keeps_two_files() -> Outcome<()> {
660	let (mut reps, mut ops, ids) = res!(stage(
661	&[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n"), (b"c.txt", b"123\n")],
662	3,
663	));
664	let (a, b, c) = (ids[0], ids[1], ids[2]);
665	let m1 = res!(reps[0].move_across(a, 0, 4, b, 1));
666	let m1_id = m1.0.id();
667	ops.push(m1);
668	let m2 = res!(reps[1].move_across(b, 0, 4, c, 1));
669	let m2_id = m2.0.id();
670	ops.push(m2);
671	let m3 = res!(reps[2].move_across(c, 0, 4, a, 1));
672	let m3_id = m3.0.id();
673	ops.push(m3);
674	let repo = res!(case(
675	"a.txt=\"a123\\nbc\\n\" b.txt=\"xyz\\n\" c.txt=\"\"",
676	&ops,
677	));
678	assert_eq!(res!(text(&repo, c)), "");
679	assert_eq!(
680	res!(text(&repo, a)).len() + res!(text(&repo, b)).len(),
681	12,
682	"every byte survives the cycle",
683	);
684	assert!(repo.flags().contains(&Flag::Won { op: m3_id }),
685	"flags were {:?}", repo.flags());
686	assert!(repo.flags().contains(&Flag::Confined { op: m1_id, home: a, denied: b }),
687	"flags were {:?}", repo.flags());
688	assert!(repo.flags().contains(&Flag::Confined { op: m2_id, home: b, denied: c }),
689	"flags were {:?}", repo.flags());
690	Ok(())
691	}
692
693	/// The cycle at length four, which is where breaking a single edge stops helping:
694	/// three files empty under that rule and one does under this one.
695	#[test]
696	fn a_four_file_cycle_keeps_three_files() -> Outcome<()> {
697	let (mut reps, mut ops, ids) = res!(stage(
698	&[
699	(b"a.txt", b"abc\n"),
700	(b"b.txt", b"xyz\n"),
701	(b"c.txt", b"123\n"),
702	(b"d.txt", b"pqr\n"),
703	],
704	4,
705	));
706	let (a, b, c, d) = (ids[0], ids[1], ids[2], ids[3]);
707	ops.push(res!(reps[0].move_across(a, 0, 4, b, 1)));
708	ops.push(res!(reps[1].move_across(b, 0, 4, c, 1)));
709	ops.push(res!(reps[2].move_across(c, 0, 4, d, 1)));
710	let m4 = res!(reps[3].move_across(d, 0, 4, a, 1));
711	let m4_id = m4.0.id();
712	ops.push(m4);
713	let repo = res!(case(
714	"a.txt=\"apqr\\nbc\\n\" b.txt=\"xyz\\n\" c.txt=\"123\\n\" d.txt=\"\"",
715	&ops,
716	));
717	assert!(repo.flags().contains(&Flag::Won { op: m4_id }),
718	"flags were {:?}", repo.flags());
719	assert_eq!(
720	repo.flags().iter().filter(\|f\| matches!(f, Flag::Confined { .. })).count(),
721	3,
722	"three of the four moves lose",
723	);
724	Ok(())
725	}
726
727	/// A cycle that stays inside one file is none of the arbitration's business, even
728	/// where the repository holds other files for it to have escaped into.
729	///
730	/// Two moves whose destinations sit inside each other's sources, both within one
731	/// file: demotion settles it, exactly as it did before the arbitration existed,
732	/// and nothing is confined.
733	#[test]
734	fn an_in_file_cycle_is_still_demoted() -> Outcome<()> {
735	let (mut reps, mut ops, ids) = res!(stage(
736	&[(b"f.txt", b"0123456789ABCDEFGHIJ"), (b"other.txt", b"kept\n")], 2));
737	let f = ids[0];
738	let (r1, r2) = reps.split_at_mut(1);
739	ops.push(res!(r1[0].move_across(f, 0, 5, f, 12)));
740	ops.push(res!(r2[0].move_across(f, 10, 5, f, 2)));
741	let repo = res!(case(
742	"f.txt=\"5678901ABCDE234FGHIJ\" other.txt=\"kept\\n\"",
743	&ops,
744	));
745	assert!(repo.flags().iter().any(\|f\| matches!(f, Flag::Demoted { .. })),
746	"an in-file cycle was not demoted: {:?}", repo.flags());
747	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Confined { .. })),
748	"an in-file cycle was confined: {:?}", repo.flags());
749	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Won { .. })),
750	"an in-file cycle was arbitrated: {:?}", repo.flags());
751	Ok(())
752	}
753
754	/// The bytes are not lost -- a slot owns them and the log holds them -- but
755	/// nothing a reader looks at renders them. That is a hazard the design note did
756	/// not name until the oracle found it, and it is what the flag exists for.
757	#[test]
758	fn content_moved_into_a_deleted_file_goes_quiet_and_says_so() -> Outcome<()> {
759	let (mut reps, mut ops, ids) = res!(stage(
760	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
761	let (a, b) = (ids[0], ids[1]);
762	let (r1, r2) = reps.split_at_mut(1);
763	let mv = res!(r1[0].move_across(a, 5, 5, b, 0));
764	let mv_id = mv.0.id();
765	ops.push(mv);
766	ops.push(res!(r2[0].remove(b)));
767	let repo = res!(case("a.txt=\"keep\\n\"", &ops));
768	// The bytes are in the deleted file, whole, and withheld.
769	assert_eq!(res!(text(&repo, b)), "move\n");
770	assert_eq!(repo.stats().withheld, 5);
771	assert!(repo.flags().contains(&Flag::MovedIntoDeleted { op: mv_id, file: b }),
772	"flags were {:?}", repo.flags());
773	Ok(())
774	}
775
776	/// A range moved from one file to a second and then to a third, with an edit
777	/// made concurrently with the first move. The edit has to arrive two files away
778	/// from where its author was looking, and it does.
779	///
780	/// This case is also where the torn flag's defect showed: the first move is
781	/// superseded by the second, by the same author, and every candidate reported it
782	/// as a race until the flag was made to consult causality.
783	#[test]
784	fn a_move_chained_through_a_third_file_carries_the_edit() -> Outcome<()> {
785	let (mut reps, mut ops, ids) = res!(stage(
786	&[(b"a.txt", LIST), (b"b.txt", b"B\n"), (b"c.txt", b"C\n")],
787	2,
788	));
789	let (a, b, c) = (ids[0], ids[1], ids[2]);
790	let (r1, r2) = reps.split_at_mut(1);
791	let first = res!(r1[0].move_across(a, 7, 7, b, 2));
792	let first_id = first.0.id();
793	ops.push(first);
794	ops.push(res!(r1[0].move_across(b, 2, 7, c, 2)));
795	ops.push(res!(r2[0].replace(a, 9, 1, b"Soy m")));
796	let repo = res!(case(
797	"a.txt=\"- Eggs\\n- Cheese\\n\" b.txt=\"B\\n\" c.txt=\"C\\n- Soy milk\\n\"",
798	&ops,
799	));
800	assert_eq!(res!(text(&repo, b)), "B\n");
801	assert_eq!(res!(text(&repo, c)), "C\n- Soy milk\n");
802	// Nothing tore: the second move was written knowing the first, so the first
803	// was superseded on purpose rather than raced.
804	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Torn { op, .. } if *op == first_id)),
805	"flags were {:?}", repo.flags());
806	Ok(())
807	}
808
809	/// A move whose source names a file's origin anchor.
810	///
811	/// No frontend can author this: the origin anchor is born dead and never appears
812	/// in a render, so nothing a user points at can name it. It is here because a
813	/// wire format has to say what a receiver does with an operation nobody meant to
814	/// send, and what it does turns out to be coherent -- the whole of one file lands
815	/// inside another, no byte lost and none duplicated. Whether the renderer should
816	/// refuse such an operation or adopt it as a file-concatenation primitive is an
817	/// open question; what is settled is that it converges and conserves.
818	#[test]
819	fn moving_a_files_origin_anchor_concatenates_the_files() -> Outcome<()> {
820	let (mut reps, mut ops, ids) = res!(stage(
821	&[(b"a.txt", b"AAA\n"), (b"b.txt", b"BBB\n")], 1));
822	let (a, b) = (ids[0], ids[1]);
823	ops.push(res!(reps[0].author(Op::Move {
824	src: vec![res!(ContentRange::new(b, 0, 1))],
825	left: Some(Anchor::origin(a)),
826	right: None,
827	})));
828	let repo = res!(case("a.txt=\"AAA\\nBBB\\n\" b.txt=\"\"", &ops));
829	assert_eq!(res!(text(&repo, b)), "");
830	Ok(())
831	}
832
833
834	// ┌───────────────────────────────────────────────────────────────────────────┐
835	// │ PROPERTIES ACROSS FILES │
836	// └───────────────────────────────────────────────────────────────────────────┘
837
838	/// What this earns is not convergence, which is nearly free where the state is
839	/// the operation set, but the repository-wide conservation invariant over
840	/// operation sets nobody wrote by hand: no byte in two files, and no live byte
841	/// nowhere, across a few hundred cross-file moves.
842	#[test]
843	fn random_multi_file_sets_render_alike_and_conserve() -> Outcome<()> {
844	let mut state = 0x2545_F491_4F6C_DD1Du64;
845	let mut next = move \|\| {
846	state = state
847	.wrapping_mul(6_364_136_223_846_793_005)
848	.wrapping_add(1_442_695_040_888_963_407);
849	(state >> 33) as usize
850	};
851	let mut moves = 0usize;
852	let mut cross = 0usize;
853	for trial in 0..40 {
854	let (mut reps, mut ops, _) = res!(stage(
855	&[(b"a.txt", b"alpha\n"), (b"b.txt", b"beta\n"), (b"c.txt", b"")],
856	3,
857	));
858	let staged = ops.len();
859	let mut upto = vec![staged; reps.len()];
860	for _ in 0..14 {
861	let who = next() % reps.len();
862	// Operations are delivered as a prefix, an operation being anchored
863	// in what its author could see, so a prefix is causally complete.
864	let target = upto[who] + next() % (ops.len() - upto[who] + 1);
865	while upto[who] < target {
866	let op = ops[upto[who]].clone();
867	res!(reps[who].recv(op));
868	upto[who] += 1;
869	}
870	let live: Vec<OpId> = {
871	let repo = res!(reps[who].seq.render());
872	repo.live().iter().map(\|f\| f.file()).collect()
873	};
874	if live.is_empty() {
875	continue;
876	}
877	let file = live[next() % live.len()];
878	let n = res!(reps[who].view(file)).len();
879	let at = if n == 0 { 0 } else { next() % (n + 1) };
880	let made = match next() % 8 {
881	0 => res!(reps[who].insert(file, at, b"[]")),
882	1 if n > at => {
883	let len = (1 + next() % 4).min(n - at);
884	res!(reps[who].delete(file, at, len))
885	},
886	2 => res!(reps[who].create(
887	&fmt!("f{}.txt", next() % 4).into_bytes())).0,
888	3 => res!(reps[who].rename(file, &fmt!("r{}.txt", next() % 4).into_bytes())),
889	4 if live.len() > 1 => res!(reps[who].remove(file)),
890	5 if n > at => {
891	let len = (1 + next() % 4).min(n - at);
892	let dest = next() % (n - len + 1);
893	moves += 1;
894	res!(reps[who].move_across(file, at, len, file, dest))
895	},
896	_ if n > at => {
897	let len = (1 + next() % 4).min(n - at);
898	let to = live[next() % live.len()];
899	let dn = res!(reps[who].view(to)).len();
900	if to != file {
901	cross += 1;
902	}
903	moves += 1;
904	res!(reps[who].move_across(file, at, len, to, next() % (dn + 1)))
905	},
906	_ => continue,
907	};
908	ops.push(made);
909	}
910	let mut want: Option<Repo> = None;
911	for round in 0..4 {
912	let mut seq = Sequence::new();
913	let mut order: Vec<usize> = (0..ops.len()).collect();
914	for i in (1..order.len()).rev() {
915	order.swap(i, next() % (i + 1));
916	}
917	for i in order {
918	res!(seq.apply(ops[i].0.clone(), ops[i].1.clone()));
919	}
920	let got = res!(seq.render());
921	res!(seq.check_conservation(&got));
922	assert_eq!(got.stats().orphaned, 0,
923	"trial {} round {} left a slot in no file", trial, round);
924	match &want {
925	None => want = Some(got),
926	Some(first) => {
927	assert_eq!(listing(first), listing(&got),
928	"trial {} round {} disagreed on the files", trial, round);
929	assert_eq!(first.flags(), got.flags(),
930	"trial {} round {} disagreed on the flags", trial, round);
931	},
932	}
933	}
934	}
935	assert!(moves > 50, "only {} moves were exercised", moves);
936	assert!(cross > 10, "only {} cross-file moves were exercised", cross);
937	Ok(())
938	}
939
940	/// Cycles planted deliberately, at every length from two to four, with and
941	/// without a concurrent edit inside a cycling block: each converges, conserves,
942	/// and leaves every confined move's content in the file its flag names.
943	///
944	/// The last of those is the property the whole rule rests on, and it is not the
945	/// same claim as convergence. A move that did not happen has to leave its bytes
946	/// where they were, and a check that only compared two replicas would agree with
947	/// itself while they went somewhere else together.
948	#[test]
949	fn planted_cross_file_cycles_leave_confined_content_at_home() -> Outcome<()> {
950	const NAMES: [&[u8]; 4] = [b"a.txt", b"b.txt", b"c.txt", b"d.txt"];
951	const TEXTS: [&[u8]; 4] = [b"abcd\n", b"wxyz\n", b"1234\n", b"pqrs\n"];
952	let mut state = 0x9e37_79b9_7f4a_7c15u64;
953	let mut next = move \|\| {
954	state = state
955	.wrapping_mul(6_364_136_223_846_793_005)
956	.wrapping_add(1_442_695_040_888_963_407);
957	(state >> 33) as usize
958	};
959	let mut planted = 0usize;
960	let mut confinements = 0usize;
961	for trial in 0..12 {
962	let k = 2 + trial % 3;
963	let staged: Vec<(&[u8], &[u8])> = (0..k).map(\|i\| (NAMES[i], TEXTS[i])).collect();
964	// One replica per move, and one more for the edit where there is one.
965	let (mut reps, mut ops, ids) = res!(stage(&staged, k as u64 + 1));
966	// Each replica moves the whole of one file into the next, at an index
967	// strictly inside what that file holds, which is what closes the loop.
968	for i in 0..k {
969	let n = res!(reps[i].view(ids[(i + 1) % k])).len();
970	let at = 1 + next() % (n - 1);
971	ops.push(res!(reps[i].move_across(ids[i], 0, n, ids[(i + 1) % k], at)));
972	planted += 1;
973	}
974	if trial % 2 == 0 {
975	// An edit inside the first file's block, concurrent with every move.
976	ops.push(res!(reps[k].insert(ids[0], 2, b"!")));
977	}
978	let repo = res!(converge(&ops));
979	for flag in repo.flags() {
980	let (op, home) = match flag {
981	Flag::Confined { op, home, .. } => (op, home),
982	_ => continue,
983	};
984	confinements += 1;
985	let named = match ops.iter().find(\|(head, _)\| head.id() == op) {
986	Some((_, o)) => o.regions().to_vec(),
987	None => return Err(err!(
988	"A flag named an operation the case did not author."; Test, Bug)),
989	};
990	let file = match repo.file(home) {
991	Some(f) => f,
992	None => return Err(err!(
993	"A confinement named a file the render does not hold."; Test, Missing)),
994	};
995	for r in &named {
996	for off in r.from()..r.to() {
997	let cid = ContentId::new(r.op(), off);
998	assert!(
999	file.runs().iter().any(\|run\| run.content.contains(&cid)),
1000	"trial {}: the confined move {} lost {} out of {}",
1001	trial, op, cid, file.path_lossy(),
1002	);
1003	}
1004	}
1005	}
1006	}
1007	assert!(planted >= 12, "only {} moves were planted", planted);
1008	assert!(confinements > 10, "only {} moves were confined", confinements);
1009	Ok(())
1010	}
1011
1012	/// A cycle with a single move in it, which winner-takes-all cannot arbitrate.
1013	///
1014	/// Whole-cycle arbitration keeps the member highest in op order, so a cycle whose
1015	/// only move is that member would keep it and break nothing. Such a move is
1016	/// confined instead, which is what every alternative rule does with it anyway.
1017	///
1018	/// The construction also shows the classifier's known false positive, stated
1019	/// rather than hidden. The move is entirely within a.txt at the time it is made,
1020	/// and it is judged to cross a boundary because the block it moves is by then made
1021	/// of bytes born in two files and it anchors inside the part born in the other
1022	/// one. The price of that reading is a confined move, which is flagged and can be
1023	/// re-issued; the price of not having it is a cycle whose members supersede an
1024	/// earlier move going unseen, and a file emptying itself.
1025	#[test]
1026	fn a_cycle_with_one_move_in_it_confines_that_move() -> Outcome<()> {
1027	let (mut reps, mut ops, ids) = res!(stage(
1028	&[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n")], 1));
1029	let (a, b) = (ids[0], ids[1]);
1030	// "xyz" out of b.txt and into the middle of a.txt, which leaves a.txt holding
1031	// bytes born in two files.
1032	ops.push(res!(reps[0].move_across(b, 0, 3, a, 1)));
1033	// The whole of a.txt to an index inside itself, which is a cycle of length one,
1034	// and the index falls inside the part born in b.txt.
1035	let mv = res!(reps[0].move_across(a, 0, 7, a, 3));
1036	let mv_id = mv.0.id();
1037	ops.push(mv);
1038	let repo = res!(case("a.txt=\"axyzbc\\n\" b.txt=\"\\n\"", &ops));
1039	assert!(repo.flags().contains(&Flag::Confined { op: mv_id, home: a, denied: a }),
1040	"flags were {:?}", repo.flags());
1041	// Confined, not won: there was nothing for it to win against.
1042	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Won { .. })),
1043	"a cycle of one move named a winner: {:?}", repo.flags());
1044	assert_eq!(res!(text(&repo, b)), "\n");
1045	Ok(())
1046	}
1047
1048	/// This is the association a recorded file field would have asserted on the
1049	/// wire, computed by the render instead. A lazy fetcher wanting one file's
1050	/// operations reads it and caches it beside the log; an index that is wrong can
1051	/// be rebuilt, and a wire field cannot.
1052	#[test]
1053	fn the_derived_index_names_one_file_per_placement() -> Outcome<()> {
1054	let (mut reps, mut ops, ids) = res!(stage(
1055	&[(b"a.txt", LIST), (b"b.txt", b"HEADER\n")], 1));
1056	let (a, b) = (ids[0], ids[1]);
1057	let mv = res!(reps[0].move_across(a, 7, 7, b, 7));
1058	let mv_id = mv.0.id();
1059	ops.push(mv);
1060	let ed = res!(reps[0].insert(b, 0, b"X"));
1061	let ed_id = ed.0.id();
1062	ops.push(ed);
1063	let mut seq = Sequence::new();
1064	for op in &ops {
1065	res!(seq.apply(op.0.clone(), op.1.clone()));
1066	}
1067	let repo = res!(seq.render());
1068	// The move named content in a.txt and landed in b.txt, which nothing on the
1069	// wire said and the forest did.
1070	assert_eq!(repo.file_of(&mv_id), Some(b));
1071	assert_eq!(repo.file_of(&ed_id), Some(b));
1072	assert_eq!(repo.file_of(&a), Some(a), "a file's own seed is in it");
1073	// Every placement is accounted for exactly once.
1074	assert_eq!(repo.index().len(), 6, "two files, two seeding splices, a move, an edit");
1075	Ok(())
1076	}
1077
1078	/// A splice anchored to a file's origin anchor lands in that file and no other,
1079	/// which is how an operation says where it goes without saying which file.
1080	#[test]
1081	fn the_origin_anchor_is_what_says_which_file() -> Outcome<()> {
1082	let (mut reps, mut ops, ids) = res!(stage(&[(b"a.txt", b""), (b"b.txt", b"")], 1));
1083	let (a, b) = (ids[0], ids[1]);
1084	// Two splices, identical but for the file their origin names.
1085	ops.push(res!(reps[0].author(Op::Splice {
1086	left: Some(Anchor::origin(a)),
1087	right: None,
1088	remove: Vec::new(),
1089	insert: b"into a".to_vec().into(),
1090	})));
1091	ops.push(res!(reps[0].author(Op::Splice {
1092	left: Some(Anchor::origin(b)),
1093	right: None,
1094	remove: Vec::new(),
1095	insert: b"into b".to_vec().into(),
1096	})));
1097	let repo = res!(case("a.txt=\"into a\" b.txt=\"into b\"", &ops));
1098	assert_eq!(res!(text(&repo, a)), "into a");
1099	assert_eq!(res!(text(&repo, b)), "into b");
1100	// The origin anchors are content, one byte each, and neither renders.
1101	assert_eq!(repo.stats().atom_bytes, 2 + 12, "one byte per file, and the two splices");
1102	assert_eq!(repo.stats().rendered, 12);
1103	Ok(())
1104	}
1105
1106	/// A file created and never written to renders empty, and its origin anchor is
1107	/// still there to be named.
1108	#[test]
1109	fn an_empty_file_is_not_empty_in_identifier_space() -> Outcome<()> {
1110	let (_, ops, ids) = res!(stage(&[(b"empty.txt", b"")], 0));
1111	let mut seq = Sequence::new();
1112	for op in &ops {
1113	res!(seq.apply(op.0.clone(), op.1.clone()));
1114	}
1115	let repo = res!(seq.render());
1116	let file = match repo.file(ids[0]) {
1117	Some(f) => f,
1118	None => return Err(err!("The file went missing."; Test, Missing)),
1119	};
1120	assert!(file.is_empty());
1121	assert!(file.is_live());
1122	assert!(file.runs().is_empty());
1123	// The gap at index zero names the origin anchor, which is the one thing an
1124	// empty file has to anchor to.
1125	assert_eq!(res!(file.gap(0)), (Some(Anchor::origin(ids[0])), None));
1126	// Which is content the set holds, one byte of it, dead.
1127	assert_eq!(repo.stats().atom_bytes, 1);
1128	assert_eq!(repo.stats().rendered, 0);
1129	assert_eq!(
1130	res!(file.splice(0, 0, b"x".to_vec())).origins().0,
1131	Some(Anchor::after(ContentId::origin(ids[0]))),
1132	);
1133	Ok(())
1134	}
1135
1136
1137	/// This is the claim the whole vocabulary rests on, stated for notes: a note
1138	/// names content, content is repository-wide, and nothing in the note ever
1139	/// mentioned a file.
1140	#[test]
1141	fn a_note_crosses_a_file_boundary_with_its_content() -> Outcome<()> {
1142	let (mut reps, mut ops, ids) = res!(stage(&[
1143	(b"a.txt", b"alpha beta gamma"),
1144	(b"b.txt", b"one two"),
1145	], 1));
1146	let (a, b) = (ids[0], ids[1]);
1147	// A note about "beta", then "beta " taken to the end of the other file.
1148	ops.push(res!(reps[0].note(a, 6, 4, b"beta needs a citation")));
1149	let repo = res!(converge(&ops));
1150	match repo.file(a) {
1151	Some(f) => assert_eq!(f.notes()[0].spans(), &[Span::new(6, 4)]),
1152	None => return Err(err!("The file went missing."; Test, Missing)),
1153	}
1154	ops.push(res!(reps[0].move_across(a, 6, 5, b, 7)));
1155	let repo = res!(case("a.txt=\"alpha gamma\" b.txt=\"one twobeta \"", &ops));
1156	// The note is no longer in the file it was written in.
1157	match repo.file(a) {
1158	Some(f) => assert!(f.notes().is_empty(), "the content left"),
1159	None => return Err(err!("The file went missing."; Test, Missing)),
1160	}
1161	// It is in the file the content went to, over the bytes it named.
1162	let dest = match repo.file(b) {
1163	Some(f) => f,
1164	None => return Err(err!("The file went missing."; Test, Missing)),
1165	};
1166	assert_eq!(dest.notes().len(), 1);
1167	assert_eq!(dest.notes()[0].spans(), &[Span::new(7, 4)]);
1168	assert_eq!(dest.notes()[0].text_lossy(), "beta needs a citation");
1169	let span = dest.notes()[0].spans()[0];
1170	assert_eq!(&dest.bytes()[span.at as usize..span.end() as usize], b"beta");
1171	// And the repository lists it once, in the one file it reaches.
1172	assert_eq!(repo.notes().len(), 1);
1173	assert!(!repo.notes()[0].on_dead());
1174	assert_eq!(repo.notes()[0].files().len(), 1);
1175	assert_eq!(repo.notes()[0].files()[0].file, b);
1176	Ok(())
1177	}
1178
1179	/// Each file says where its share of the content is, and the repository says the
1180	/// note is in two places.
1181	#[test]
1182	fn a_note_torn_across_two_files_is_listed_once() -> Outcome<()> {
1183	let (mut reps, mut ops, ids) = res!(stage(&[
1184	(b"a.txt", b"0123456789"),
1185	(b"b.txt", b"----"),
1186	], 1));
1187	let (a, b) = (ids[0], ids[1]);
1188	ops.push(res!(reps[0].note(a, 2, 6, b"about 234567")));
1189	// Half of the noted run goes to the other file.
1190	ops.push(res!(reps[0].move_across(a, 4, 3, b, 2)));
1191	let repo = res!(case("a.txt=\"0123789\" b.txt=\"--456--\"", &ops));
1192	// "23" and "7" are what is left in a, and the move closed the gap between
1193	// them, so they are one region of the render and one span: a span is a run of
1194	// rendered bytes, not a run of content.
1195	match repo.file(a) {
1196	Some(f) => assert_eq!(f.notes()[0].spans(), &[Span::new(2, 3)]),
1197	None => return Err(err!("The file went missing."; Test, Missing)),
1198	}
1199	// Put something between them, and the note is in two places in one file.
1200	ops.push(res!(reps[0].insert(a, 4, b"\|")));
1201	let repo = res!(case("a.txt=\"0123\|789\" b.txt=\"--456--\"", &ops));
1202	let left = match repo.file(a) {
1203	Some(f) => f,
1204	None => return Err(err!("The file went missing."; Test, Missing)),
1205	};
1206	let right = match repo.file(b) {
1207	Some(f) => f,
1208	None => return Err(err!("The file went missing."; Test, Missing)),
1209	};
1210	// "23" stayed, "456" left, "7" stayed: two spans in one file, one in the
1211	// other, and six bytes in all.
1212	assert_eq!(left.notes().len(), 1);
1213	assert_eq!(left.notes()[0].spans(), &[Span::new(2, 2), Span::new(5, 1)]);
1214	assert_eq!(right.notes().len(), 1);
1215	assert_eq!(right.notes()[0].spans(), &[Span::new(2, 3)]);
1216	// One note, in two files, over the six bytes it named.
1217	assert_eq!(repo.notes().len(), 1);
1218	let note = &repo.notes()[0];
1219	assert!(!note.on_dead());
1220	assert_eq!(note.files().len(), 2);
1221	assert_eq!(note.files()[0].file, a);
1222	assert_eq!(note.files()[1].file, b);
1223	let total: u64 = note.files().iter()
1224	.flat_map(\|p\| p.spans.iter())
1225	.map(\|s\| s.len)
1226	.sum();
1227	assert_eq!(total, 6, "no byte of the noted run went missing");
1228	assert_eq!(note.spans_in(b), &[Span::new(2, 3)]);
1229	assert!(note.spans_in(OpId::default()).is_empty());
1230	Ok(())
1231	}
1232
1233	/// The bytes still render, into a file no reader looks at, and that is what the
1234	/// flag beside it says.
1235	#[test]
1236	fn a_note_in_a_deleted_file_is_not_a_note_on_dead_content() -> Outcome<()> {
1237	let (mut reps, mut ops, ids) = res!(stage(&[
1238	(b"a.txt", b"keep this line"),
1239	(b"b.txt", b""),
1240	], 1));
1241	let (a, b) = (ids[0], ids[1]);
1242	ops.push(res!(reps[0].note(a, 5, 4, b"about this")));
1243	ops.push(res!(reps[0].move_across(a, 5, 4, b, 0)));
1244	ops.push(res!(reps[0].remove(b)));
1245	let repo = res!(converge(&ops));
1246	// The deleted file still holds the bytes, and still resolves the note.
1247	let gone = match repo.file(b) {
1248	Some(f) => f,
1249	None => return Err(err!("The file went missing."; Test, Missing)),
1250	};
1251	assert!(!gone.is_live());
1252	assert_eq!(gone.text_lossy(), "this");
1253	assert_eq!(gone.notes().len(), 1);
1254	assert_eq!(gone.notes()[0].spans(), &[Span::new(0, 4)]);
1255	// So the note is placed, not dead, and the repository says which file.
1256	assert_eq!(repo.notes().len(), 1);
1257	assert!(!repo.notes()[0].on_dead());
1258	assert!(repo.dead_notes().is_empty());
1259	assert_eq!(repo.notes()[0].files()[0].file, b);
1260	Ok(())
1261	}
1262
1263	/// A note names content, and content the operation set does not hold is a hole
1264	/// in the history rather than a note on nothing.
1265	#[test]
1266	fn a_note_on_content_the_set_lacks_is_refused() -> Outcome<()> {
1267	let (mut reps, mut ops, ids) = res!(stage(&[(b"a.txt", b"alpha beta")], 1));
1268	let note = res!(reps[0].note(ids[0], 0, 5, b"about alpha"));
1269	// The whole set renders; the set without the splice the note names does not.
1270	ops.push(note.clone());
1271	res!(converge(&ops));
1272	let mut seq = Sequence::new();
1273	res!(seq.apply(ops[0].0.clone(), ops[0].1.clone()));
1274	res!(seq.apply(note.0.clone(), note.1.clone()));
1275	assert!(seq.render().is_err(),
1276	"a note whose subject has not arrived cannot be told from a note on \
1277	content that has died");
1278	Ok(())
1279	}
1280
1281
1282	// ┌───────────────────────────────────────────────────────────────────────────┐
1283	// │ THE SILENT-DELETION CASES │
1284	// └───────────────────────────────────────────────────────────────────────────┘
1285	//
1286	// The self-hosting trial's two silent rounds, reproduced exactly: work that is
1287	// durable in the log and invisible in the converged tree must be flagged, and a
1288	// deletion causally ordered with the work -- supersession -- must not be. The
1289	// rendered bytes in every case here are what the engine rendered before the
1290	// flags existed; the flags are reportage, not placement.
1291
1292	/// The trial's round four. Replica one records a cross-file block move the way
1293	/// a diff-based capture does -- a deletion in one file and a fresh insertion in
1294	/// another, with no move operation -- while replica two concurrently edits
1295	/// inside the block. The edit's anchors die with the block, its bytes strand at
1296	/// the deletion site, and the flag names both operations.
1297	#[test]
1298	fn an_edit_inside_a_captured_move_strands_and_is_flagged() -> Outcome<()> {
1299	let (mut reps, mut ops, ids) = res!(stage(
1300	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
1301	let (a, b) = (ids[0], ids[1]);
1302	let (r1, r2) = reps.split_at_mut(1);
1303	// The captured "move": splice the block out of a.txt, splice its bytes into
1304	// b.txt, and say nothing about the two being one intent.
1305	let del = res!(r1[0].delete(a, 5, 5));
1306	let del_id = del.0.id();
1307	ops.push(del);
1308	ops.push(res!(r1[0].insert(b, 0, b"move\n")));
1309	// The concurrent edit inside the block.
1310	let edit = res!(r2[0].insert(a, 7, b"XY"));
1311	let edit_id = edit.0.id();
1312	ops.push(edit);
1313	// The block lands unedited, and the edit strands where the block was.
1314	let repo = res!(case("a.txt=\"keep\\nXY\" b.txt=\"move\\n\"", &ops));
1315	assert!(repo.flags().contains(&Flag::Stranded { op: edit_id, by: del_id }),
1316	"flags were {:?}", repo.flags());
1317	// The file the sliver renders in keeps the flag, so a reader of a.txt is
1318	// told without asking the repository.
1319	let stranded_in_a = match repo.file(a) {
1320	Some(f) => f.flags().contains(&Flag::Stranded { op: edit_id, by: del_id }),
1321	None => false,
1322	};
1323	assert!(stranded_in_a, "a.txt did not keep the flag");
1324	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::SplicedIntoDeleted { .. })),
1325	"no file was deleted: {:?}", repo.flags());
1326	Ok(())
1327	}
1328
1329	/// The trial's round five. Replica one deletes a file; replica two concurrently
1330	/// edits inside it. The file is gone from both trees, the edit renders only
1331	/// into the deleted file, and the flag names the edit, the file and the
1332	/// deletion.
1333	#[test]
1334	fn an_edit_inside_a_concurrently_deleted_file_is_flagged() -> Outcome<()> {
1335	let (mut reps, mut ops, ids) = res!(stage(
1336	&[(b"a.txt", b"fn main() {}\n")], 2));
1337	let a = ids[0];
1338	let (r1, r2) = reps.split_at_mut(1);
1339	let del = res!(r1[0].remove(a));
1340	let del_id = del.0.id();
1341	ops.push(del);
1342	let edit = res!(r2[0].insert(a, 11, b" ok"));
1343	let edit_id = edit.0.id();
1344	ops.push(edit);
1345	// No live files, and the edit whole inside the withheld render.
1346	let repo = res!(case("", &ops));
1347	assert_eq!(res!(text(&repo, a)), "fn main() { ok}\n");
1348	assert_eq!(repo.stats().withheld, 16);
1349	assert!(repo.flags().contains(
1350	&Flag::SplicedIntoDeleted { op: edit_id, file: a, del: del_id }),
1351	"flags were {:?}", repo.flags());
1352	// The deleted file keeps the flag, so a recovery verb has it to hand.
1353	let kept = match repo.file(a) {
1354	Some(f) => f.flags().contains(
1355	&Flag::SplicedIntoDeleted { op: edit_id, file: a, del: del_id }),
1356	None => false,
1357	};
1358	assert!(kept, "a.txt did not keep the flag");
1359	// The file's own deletion killed no anchor, so nothing is stranded.
1360	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Stranded { .. })),
1361	"flags were {:?}", repo.flags());
1362	Ok(())
1363	}
1364
1365	/// The region-level supersession control: the same shape as the stranded case,
1366	/// but the deletion was written in knowledge of the edit. A deleter who could
1367	/// see the insertion chose to remove the region around it, and is owed no flag
1368	/// for a race that did not happen.
1369	#[test]
1370	fn a_deletion_that_saw_the_edit_supersedes_and_raises_nothing() -> Outcome<()> {
1371	let (mut reps, mut ops, ids) = res!(stage(
1372	&[(b"a.txt", b"keep\nmove\n")], 2));
1373	let a = ids[0];
1374	let (r1, r2) = reps.split_at_mut(1);
1375	let edit = res!(r2[0].insert(a, 7, b"XY"));
1376	res!(r1[0].recv(edit.clone()));
1377	ops.push(edit);
1378	// Replica one deletes the whole block, the insertion included, seeing it.
1379	ops.push(res!(r1[0].delete(a, 5, 7)));
1380	let repo = res!(case("a.txt=\"keep\\n\"", &ops));
1381	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::Stranded { .. })),
1382	"an informed deletion was flagged as a race: {:?}", repo.flags());
1383	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::SplicedIntoDeleted { .. })),
1384	"flags were {:?}", repo.flags());
1385	Ok(())
1386	}
1387
1388	/// The file-level supersession controls, both ways round. A deleter who had
1389	/// seen the edit deleted it on purpose; an editor who had seen the deletion
1390	/// wrote into a file they knew was dead. Neither is a race, and neither flags.
1391	#[test]
1392	fn a_file_deletion_ordered_with_the_edit_raises_nothing() -> Outcome<()> {
1393	// The deletion after the edit, seeing it.
1394	let (mut reps, mut ops, ids) = res!(stage(
1395	&[(b"a.txt", b"fn main() {}\n")], 2));
1396	let a = ids[0];
1397	{
1398	let (r1, r2) = reps.split_at_mut(1);
1399	let edit = res!(r2[0].insert(a, 11, b" ok"));
1400	res!(r1[0].recv(edit.clone()));
1401	ops.push(edit);
1402	ops.push(res!(r1[0].remove(a)));
1403	}
1404	let repo = res!(case("", &ops));
1405	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::SplicedIntoDeleted { .. })),
1406	"an informed deletion was flagged as a race: {:?}", repo.flags());
1407
1408	// The edit after the deletion, seeing it.
1409	let (mut reps, mut ops, ids) = res!(stage(
1410	&[(b"a.txt", b"fn main() {}\n")], 2));
1411	let a = ids[0];
1412	{
1413	let (r1, r2) = reps.split_at_mut(1);
1414	let del = res!(r1[0].remove(a));
1415	res!(r2[0].recv(del.clone()));
1416	ops.push(del);
1417	ops.push(res!(r2[0].insert(a, 11, b" ok")));
1418	}
1419	let repo = res!(case("", &ops));
1420	assert!(!repo.flags().iter().any(\|f\| matches!(f, Flag::SplicedIntoDeleted { .. })),
1421	"an informed edit was flagged as a race: {:?}", repo.flags());
1422	Ok(())
1423	}
1424
1425	/// The same collision with the move recorded as a move: the edit follows the
1426	/// block into the other file, nothing strands, and neither of the deletion
1427	/// flags has anything to say. This is the round the trial says the engine was
1428	/// built for, and the new flags must leave it alone.
1429	#[test]
1430	fn a_recorded_move_carries_the_edit_and_the_new_flags_stay_quiet() -> Outcome<()> {
1431	let (mut reps, mut ops, ids) = res!(stage(
1432	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
1433	let (a, b) = (ids[0], ids[1]);
1434	let (r1, r2) = reps.split_at_mut(1);
1435	ops.push(res!(r1[0].move_across(a, 5, 5, b, 0)));
1436	ops.push(res!(r2[0].insert(a, 7, b"XY")));
1437	let repo = res!(case("a.txt=\"keep\\n\" b.txt=\"moXYve\\n\"", &ops));
1438	assert!(!repo.flags().iter().any(\|f\| matches!(f,
1439	Flag::Stranded { .. } \| Flag::SplicedIntoDeleted { .. })),
1440	"flags were {:?}", repo.flags());
1441	Ok(())
1442	}
1443
1444	/// A move into a concurrently deleted file is [`Flag::MovedIntoDeleted`]'s
1445	/// territory, and stays so: the new flags concern splices, and the file's own
1446	/// content ops, all causally before the deletion, raise nothing either.
1447	#[test]
1448	fn moved_into_deleted_keeps_its_territory() -> Outcome<()> {
1449	let (mut reps, mut ops, ids) = res!(stage(
1450	&[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"B\n")], 2));
1451	let (a, b) = (ids[0], ids[1]);
1452	let (r1, r2) = reps.split_at_mut(1);
1453	let mv = res!(r1[0].move_across(a, 5, 5, b, 0));
1454	let mv_id = mv.0.id();
1455	ops.push(mv);
1456	ops.push(res!(r2[0].remove(b)));
1457	let repo = res!(case("a.txt=\"keep\\n\"", &ops));
1458	assert!(repo.flags().contains(&Flag::MovedIntoDeleted { op: mv_id, file: b }),
1459	"flags were {:?}", repo.flags());
1460	// b.txt's own seed content went dark too, but its author's edit was seen by
1461	// the deleter: supersession, not a race, and not a flag.
1462	assert!(!repo.flags().iter().any(\|f\| matches!(f,
1463	Flag::Stranded { .. } \| Flag::SplicedIntoDeleted { .. })),
1464	"flags were {:?}", repo.flags());
1465	Ok(())
1466	}
1467
1468	/// A mode is asserted of a file's identity, so it survives everything that
1469	/// happens to the file's path and to its bytes.
1470	///
1471	/// This is the whole argument for [`Op::FileMode`] being shaped like a rename
1472	/// rather than being a field on one. The script is made executable once; it is
1473	/// then renamed, edited, and edited again by another replica, and it is still
1474	/// executable, because none of those operations said anything about what it is.
1475	#[test]
1476	fn a_mode_survives_a_rename_and_an_edit() -> Outcome<()> {
1477	let (mut reps, mut ops, ids) = res!(stage(&[(b"build.sh", b"#!/bin/sh\n")], 2));
1478	let a = ids[0];
1479	let (r1, r2) = reps.split_at_mut(1);
1480	ops.push(res!(r1[0].set_mode(a, Mode::Executable)));
1481	ops.push(res!(r1[0].rename(a, b"tools/build.sh")));
1482	ops.push(res!(r2[0].insert(a, 10, b"set -e\n")));
1483	let repo = res!(case(
1484	"tools/build.sh[executable]=\"#!/bin/sh\\nset -e\\n\"", &ops));
1485	let f = match repo.file(a) {
1486	Some(f) => f,
1487	None => return Err(err!("The file went missing."; Test, Missing)),
1488	};
1489	assert_eq!(f.mode(), Mode::Executable);
1490	Ok(())
1491	}
1492
1493	#[test]
1494	fn a_file_nobody_named_is_normal() -> Outcome<()> {
1495	let (mut reps, mut ops, ids) = res!(stage(&[(b"a.txt", b"hello\n")], 1));
1496	let a = ids[0];
1497	ops.push(res!(reps[0].insert(a, 5, b" there")));
1498	let repo = res!(case("a.txt=\"hello there\\n\"", &ops));
1499	match repo.file(a) {
1500	Some(f) => assert_eq!(f.mode(), Mode::Normal),
1501	None => return Err(err!("The file went missing."; Test, Missing)),
1502	}
1503	Ok(())
1504	}
1505
1506	/// Two replicas saying different things about one file at once settle the way
1507	/// two concurrent renames settle: by operation order, the same answer whatever
1508	/// order the operations arrive in.
1509	#[test]
1510	fn concurrent_modes_settle_by_op_order() -> Outcome<()> {
1511	let (mut reps, mut ops, ids) = res!(stage(&[(b"s.sh", b"x\n")], 2));
1512	let a = ids[0];
1513	let (r1, r2) = reps.split_at_mut(1);
1514	let one = res!(r1[0].set_mode(a, Mode::Executable));
1515	let two = res!(r2[0].set_mode(a, Mode::Symlink));
1516	// Neither saw the other, and the later in op order is the one that stands.
1517	let later = if OpOrder::of(&one.0.id()) > OpOrder::of(&two.0.id()) {
1518	Mode::Executable
1519	} else {
1520	Mode::Symlink
1521	};
1522	ops.push(one);
1523	ops.push(two);
1524	let repo = res!(converge(&ops));
1525	match repo.file(a) {
1526	Some(f) => assert_eq!(f.mode(), later, "the later assertion stands"),
1527	None => return Err(err!("The file went missing."; Test, Missing)),
1528	}
1529	// Setting a mode back is an ordinary later assertion, not a special case.
1530	ops.push(res!(reps[0].set_mode(a, Mode::Normal)));
1531	let repo = res!(converge(&ops));
1532	match repo.file(a) {
1533	Some(f) => assert_eq!(f.mode(), Mode::Normal),
1534	None => return Err(err!("The file went missing."; Test, Missing)),
1535	}
1536	Ok(())
1537	}
1538
1539	/// The message says the set is not causally complete.
1540	///
1541	/// The same refusal a rename and a delete get, for the same reason: the render
1542	/// cannot say what it does not hold.
1543	#[test]
1544	fn a_mode_of_an_absent_file_is_refused() -> Outcome<()> {
1545	let mut seq = Sequence::new();
1546	let ghost = OpId::new(ReplicaId::new(9), 1);
1547	res!(seq.apply(
1548	Header::root(OpId::new(ReplicaId::new(1), 1)),
1549	Op::FileMode { file: ghost, mode: Mode::Executable },
1550	));
1551	let e = match seq.render() {
1552	Ok(_) => return Err(err!("A mode of an absent file rendered."; Test)),
1553	Err(e) => e,
1554	};
1555	let msg = fmt!("{}", e);
1556	assert!(msg.contains("causally complete"), "message was {}", msg);
1557	assert!(msg.contains(&fmt!("{}", ghost)), "message was {}", msg);
1558	Ok(())
1559	}
1560