oxedyne/fe2o3 — fe2o3_ore/src/seq/mod.rs

58.3 KiB, 453 runs

created by r1870400018:17912, 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	//! A convergent repository in which a move is recorded as a move.
2	//!
3	//! Bytes take their identity from the splice that created them and never lose
4	//! it. Position is a separate, derived layer: an ordered set of slots, each
5	//! claiming a run of byte identities, ordered against each other by Fugue over
6	//! origins that name content rather than positions. A move mints new slots at
7	//! the destination and claims the moved bytes for them; a per-byte
8	//! last-writer-wins register decides which slot owns each byte, so two
9	//! concurrent moves of one run cannot duplicate it. Because an insertion's
10	//! origin names a byte, and that byte's owning slot is wherever it currently
11	//! lives, the insertion follows the move without anything being written to make
12	//! it do so.
13	//!
14	//! # A file is a subtree
15	//!
16	//! There is one forest for the whole repository, and its root children are the
17	//! files' origin anchors: one byte per file, born dead, minted by the
18	//! [`Op::FileCreate`] whose identity is the file's identity. A file is the
19	//! subtree beneath one of them, so a slot's file is read off the tree rather
20	//! than off the record, and no operation carries a file at all.
21	//!
22	//! Two consequences are the point of the arrangement. A move between files needs
23	//! no routing, because its destination anchor already names content in the file
24	//! it lands in; and an edit made concurrently inside a range that moves between
25	//! files follows it, for exactly the reason it follows an in-file move -- its
26	//! anchor never mentioned a file either.
27	//!
28	//! # What it guarantees, and what it does not
29	//!
30	//! Two replicas that have applied the same operations render the same bytes,
31	//! whatever order the operations arrived in. That is the whole of the promise.
32	//! It is not a promise that the result is what either author wanted:
33	//!
34	//! - Two moves of the same run leave one copy, at the destination of whichever
35	//! move is higher in op order. The loser's intent is discarded, and flagged.
36	//! - Two moves of partly overlapping runs tear at the overlap. Both halves
37	//! survive, in two places, which is deterministic and is almost certainly not
38	//! what either author meant. It is flagged.
39	//! - Two moves whose destinations sit inside each other's sources form a cycle.
40	//! Inside one file it is broken by demotion: one move lands where its anchor
41	//! content was originally written rather than where it now lives, which is
42	//! flagged. Where the cycle crosses a file boundary it is arbitrated instead,
43	//! as one concurrent group: the member highest in op order completes, and every
44	//! other member is confined -- its claims are not written, so its content stays
45	//! where it was, and both files are told by [`Flag::Confined`]. Nothing has to be
46	//! undone, because nothing was done.
47	//! - Two splices that concurrently named overlapping content are arbitrated as
48	//! one group, so that the contended region holds whole hunks rather than two
49	//! authors' bytes interleaved. The member highest in op order prevails; every
50	//! member concurrent with it yields, its removals not burying and its
51	//! insertion buried whole, and [`Flag::Yielded`] names the group and its
52	//! maximum. A member in the winner's causal past keeps its work, which is what
53	//! leaves a winner's own earlier hunks alone -- and is also why the region is a
54	//! promise of whole hunks and not a promise of one author. [`Flag::Overlap`]
55	//! still fires beneath the arbitration, as the raw fact it always was.
56	//! - Content moved into a file that has been deleted renders nowhere a reader
57	//! looks. Nothing is lost and [`Flag::MovedIntoDeleted`] says so.
58	//! - An insertion whose every anchored neighbour was deleted by a concurrent
59	//! operation renders as a fragment at the deletion site, its context gone.
60	//! Nothing is lost and [`Flag::Stranded`] says so, naming both operations.
61	//! - An edit concurrent with the deletion of its own file renders only into the
62	//! deleted file, which no reader looks at. Nothing is lost and
63	//! [`Flag::SplicedIntoDeleted`] says so, naming the edit and the deletion. A
64	//! deletion causally ordered with the edit -- either seeing the other -- is a
65	//! decision rather than a race, and raises nothing.
66	//!
67	//! The posture is to converge always and to say what happened always. Every
68	//! [`render::Flag`] is a function of the operation set, so a flag is a fact
69	//! about the history rather than a note about this run of the renderer.
70	//!
71	//! # Transient by construction
72	//!
73	//! The durable record is the operation log. Everything here -- the atoms, the
74	//! claim register, the tombstones, the slots, their order -- is derived, and is
75	//! rebuilt from the operation set on every render. A [`Sequence`] is therefore
76	//! an accumulator and nothing more: applying an operation is set insertion, and
77	//! two sequences holding the same operations are the same sequence whatever
78	//! order they were built in.
79	//!
80	//! # Preconditions
81	//!
82	//! Rendering requires a causally complete operation set, and that is checked
83	//! against the operations' own parents rather than inferred from what they happen
84	//! to name. Every parent must be present, and so must every atom whose content an
85	//! anchor or a range names, the origin anchors of the files included. An anchor
86	//! naming an atom that has not arrived cannot be resolved, and rather than guess,
87	//! the render fails and says which operation named what. [`crate::log::OpLog`]
88	//! supplies a closed set by construction; a caller assembling operations by hand
89	//! must arrange it.
90	//!
91	//! Rendering also lays out the whole repository, because ordering is
92	//! repository-wide. Laying out only the closure of one file's origin anchor under
93	//! the claim register would suffice and would usually be the file's own
94	//! operations; that is design work owed, and until it is done, opening one file
95	//! costs the repository.
96	//!
97	//! # Op order
98	//!
99	//! Every tie-break in the structure is decided by [`OpOrder`], the pair
100	//! `(counter, replica)` ascending. Convergence needs only that the order is
101	//! total, which it is for any counters at all; the intuition that a later edit
102	//! wins needs the counter to be a Lamport clock, one greater than the greatest
103	//! the replica has seen. [`crate::log::OpLog::next_counter`] mints exactly that,
104	//! so an author who takes identifiers from the log gets the intuition for
105	//! nothing; an author minting its own is responsible for the same rule.
106	//!
107	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
108	//! Anthropic Claude
109
110	pub mod atom;
111	pub mod claim;
112	pub mod render;
113	pub mod slot;
114
115	#[cfg(test)]
116	mod file_tests;
117	#[cfg(test)]
118	mod overlap_tests;
119	#[cfg(test)]
120	mod tests;
121	#[cfg(test)]
122	mod forget_tests;
123
124	use crate::id::{
125	ContentId,
126	ContentRange,
127	OpId,
128	ReplicaId,
129	};
130	use crate::log::Causality;
131	use crate::op::{
132	Header,
133	Mode,
134	Op,
135	Placing,
136	Record,
137	Stub,
138	};
139	use crate::seq::atom::Atoms;
140	use crate::seq::claim::{
141	Claims,
142	Dead,
143	};
144	use crate::seq::render::{
145	Flag,
146	Rendered,
147	Repo,
148	Run,
149	Stats,
150	};
151	use crate::seq::slot::Slots;
152
153	use oxedyne_fe2o3_core::prelude::*;
154	use oxedyne_fe2o3_data::interval::IntervalMap;
155
156	use std::collections::{
157	BTreeMap,
158	BTreeSet,
159	};
160	use std::ops::Range;
161
162
163	/// The total order every tie-break in the structure is decided by: the Lamport
164	/// counter first, the authoring replica second.
165	///
166	/// This is deliberately not the order on [`OpId`], which sorts by replica first
167	/// and is meant for indexing. Sorting by counter first is what makes "the later
168	/// edit wins" mean what it says.
169	#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
170	pub struct OpOrder {
171	pub counter: u64, // which decides
172	pub replica: u64, // which breaks the tie
173	}
174
175	impl OpOrder {
176	pub fn of(id: &OpId) -> Self {
177	Self {
178	counter: id.counter,
179	replica: id.replica.inner(),
180	}
181	}
182	}
183
184
185	/// An operation as the sequence holds it: what it says, and what its author had
186	/// seen when they said it.
187	#[derive(Clone, Debug, Eq, PartialEq)]
188	struct Applied {
189	parents: Vec<OpId>, // the author's frontier when it was written
190	op: Op,
191	}
192
193
194	/// What the lifecycle operations say about one file.
195	#[derive(Clone, Debug, Eq, PartialEq)]
196	struct FileInfo {
197	path: Vec<u8>, // after every rename the set holds
198	mode: Mode, // after every mode assertion the set holds
199	live: bool, // whether it still exists
200	}
201
202
203	/// A repository's worth of operations, and the state they describe.
204	///
205	/// The state is the operation set and nothing else, so applying an operation is
206	/// idempotent, commutative and cheap, and the files themselves are computed by
207	/// [`Sequence::render`] when they are wanted. There is one sequence per
208	/// repository rather than one per file: a file is a subtree of the forest the
209	/// render lays out, and which subtree a slot is in is not knowable until the
210	/// forest is laid out.
211	#[derive(Clone, Debug, Default, Eq, PartialEq)]
212	pub struct Sequence {
213	ops: BTreeMap<OpId, Applied>, // by identity
214	forgotten: BTreeMap<OpId, Placing>, // what every Forget in the set says
215	}
216
217	impl Sequence {
218
219	pub fn new() -> Self {
220	Self { ops: BTreeMap::new(), forgotten: BTreeMap::new() }
221	}
222
223	/// Builds a repository from an operation set, in any order.
224	pub fn build<I>(ops: I)
225	-> Outcome<Self>
226	where
227	I: IntoIterator<Item = (Header, Op)>,
228	{
229	let mut seq = Self::new();
230	for (head, op) in ops {
231	res!(seq.apply(head, op));
232	}
233	Ok(seq)
234	}
235
236	/// Applies an operation under the header that names it.
237	///
238	/// Applying the same operation twice does nothing the second time. Applying
239	/// two different operations under one identity is refused: an identity names
240	/// one operation, and a structure that quietly kept the first would converge
241	/// on whichever replica saw which. Two headers differing only in their
242	/// parents are two different operations for the same reason.
243	pub fn apply(&mut self, head: Header, op: Op)
244	-> Outcome<()>
245	{
246	res!(op.validate());
247	let id = head.id();
248	// A forget is applied to the set as much as to itself: every operation
249	// it names is held from now on in the shape the forget says, whether
250	// the original was here first or arrives later, and whether what arrives
251	// is the original or the stub a repack wrote. That is what makes the
252	// set a function of its members and nothing else -- two replicas that
253	// hold the same operations and the same forgets render the same bytes,
254	// and it does not matter which of them still has the forgotten bytes on
255	// its disk.
256	if let Op::Forget { of, .. } = &op {
257	res!(self.forget(of));
258	}
259	let op = match self.forgotten.get(&id) {
260	Some(placing) => Op::Forgotten { placing: placing.clone() },
261	None => op,
262	};
263	let applied = Applied { parents: head.parents().to_vec(), op };
264	match self.ops.get(&id) {
265	Some(seen) if *seen != applied => Err(err!(
266	"The identity {} already names a different {}; an operation \
267	identity names one operation.", id, seen.op.name();
268	Invalid, Input, Conflict)),
269	Some(_) => Ok(()),
270	None => {
271	self.ops.insert(id, applied);
272	Ok(())
273	},
274	}
275	}
276
277	/// Holds every operation the stubs name in the shape they say, from now on
278	/// and whether the original is here yet or not.
279	///
280	/// This is what applying a [`Op::Forget`] does to the set, split out so that
281	/// it can be done without the forget itself joining the set: a state older
282	/// than the forget, rendered from the ancestry of a mark, holds none of the
283	/// forget's parents and cannot carry the forget, and must still not show
284	/// what was forgotten. The bytes are gone from every state there ever was,
285	/// which is what forgetting means.
286	pub fn forget(&mut self, of: &[Stub])
287	-> Outcome<()>
288	{
289	for stub in of {
290	match self.forgotten.get(&stub.id) {
291	Some(seen) if *seen != stub.placing => return Err(err!(
292	"The operation {} is said to keep one shape by one forget and \
293	another by another; a forgotten operation keeps one shape.", stub.id;
294	Invalid, Input, Conflict)),
295	_ => (),
296	}
297	}
298	for stub in of {
299	self.forgotten.insert(stub.id, stub.placing.clone());
300	if let Some(held) = self.ops.get_mut(&stub.id) {
301	held.op = Op::Forgotten { placing: stub.placing.clone() };
302	}
303	}
304	Ok(())
305	}
306
307	/// Every stub the forgets in this set have said, ascending by identifier.
308	pub fn forgotten(&self) -> Vec<Stub> {
309	self.forgotten.iter()
310	.map(\|(id, placing)\| Stub { id: *id, placing: placing.clone() })
311	.collect()
312	}
313
314	/// Takes every operation of another repository, and returns how many of them
315	/// were new.
316	///
317	/// This is what a merge is. The state is the operation set and nothing else,
318	/// so two branches meet by taking the union of their sets, and the render of
319	/// the union is the convergent merge -- which is a fact about the two sets and
320	/// not about which branch absorbed which.
321	///
322	/// Nothing is asked of the two sets causally. Closure is checked where it
323	/// matters, at [`Sequence::render_with`], against the graph the caller holds.
324	///
325	/// An identity naming a different operation in each set is refused, for the
326	/// reason [`Sequence::apply`] refuses it, and nothing at all is taken: the two
327	/// sets are not two versions of one history and no part of the merge is worth
328	/// keeping.
329	pub fn absorb(&mut self, other: &Self)
330	-> Outcome<usize>
331	{
332	// The forgets of both sides first, since they decide the shape every
333	// operation is compared in: an original on one side and its stub on the
334	// other are one operation, not two.
335	let mut forgotten = self.forgotten.clone();
336	for (id, placing) in &other.forgotten {
337	match forgotten.get(id) {
338	Some(seen) if seen != placing => return Err(err!(
339	"The operation {} is forgotten in one shape in one repository and \
340	in another shape in the other; a forgotten operation keeps one \
341	shape, so the two are not branches of one history.", id;
342	Invalid, Input, Conflict)),
343	_ => {
344	forgotten.insert(*id, placing.clone());
345	},
346	}
347	}
348	let shaped = \|id: &OpId, applied: &Applied\| -> Applied {
349	match forgotten.get(id) {
350	Some(p) => Applied {
351	parents: applied.parents.clone(),
352	op: Op::Forgotten { placing: p.clone() },
353	},
354	None => applied.clone(),
355	}
356	};
357	let mut fresh: Vec<(OpId, Applied)> = Vec::new();
358	for (id, applied) in &other.ops {
359	let theirs = shaped(id, applied);
360	match self.ops.get(id) {
361	Some(seen) if shaped(id, seen) != theirs => return Err(err!(
362	"The identity {} names a {} in one repository and a {} in the \
363	other; an operation identity names one operation, so the two are \
364	not branches of one history.", id, seen.op.name(), theirs.op.name();
365	Invalid, Input, Conflict)),
366	Some(_) => (),
367	None => fresh.push((*id, theirs)),
368	}
369	}
370	let n = fresh.len();
371	for (id, applied) in fresh {
372	self.ops.insert(id, applied);
373	}
374	for (id, applied) in self.ops.iter_mut() {
375	if let Some(p) = forgotten.get(id) {
376	applied.op = Op::Forgotten { placing: p.clone() };
377	}
378	}
379	self.forgotten = forgotten;
380	Ok(n)
381	}
382
383	/// Applies a durable record.
384	///
385	/// Everything the log holds belongs here, because the repository is what the
386	/// structure now models: a file's creation mints its origin anchor, a rename
387	/// changes its path, a deletion retires it, and the two content operations
388	/// place bytes. Only a mark says nothing about any of it, and it is kept
389	/// anyway so that the causal graph the render is judged by is not full of
390	/// holes.
391	pub fn apply_record(&mut self, rec: &Record)
392	-> Outcome<()>
393	{
394	self.apply(rec.head.clone(), rec.op.clone())
395	}
396
397	pub fn len(&self) -> usize {
398	self.ops.len()
399	}
400
401	pub fn is_empty(&self) -> bool {
402	self.ops.is_empty()
403	}
404
405	pub fn contains(&self, id: &OpId) -> bool {
406	self.ops.contains_key(id)
407	}
408
409	pub fn get(&self, id: &OpId)
410	-> Option<&Op>
411	{
412	self.ops.get(id).map(\|a\| &a.op)
413	}
414
415	pub fn parents_of(&self, id: &OpId)
416	-> Option<&[OpId]>
417	{
418	self.ops.get(id).map(\|a\| a.parents.as_slice())
419	}
420
421	/// Iterates the operations, in ascending order of identity.
422	pub fn iter(&self)
423	-> impl Iterator<Item = (&OpId, &Op)>
424	{
425	self.ops.iter().map(\|(id, a)\| (id, &a.op))
426	}
427
428	pub fn causality(&self)
429	-> Causality<'_>
430	{
431	Causality::new(self.ops.iter().map(\|(id, a)\| (*id, a.parents.as_slice())))
432	}
433
434	/// The operations in op order, which is the order every stage of the render
435	/// reads them in.
436	fn in_op_order(&self) -> Vec<(OpId, &Op)> {
437	let mut ops: Vec<(OpId, &Op)> = self.ops.iter()
438	.map(\|(id, a)\| (*id, &a.op))
439	.collect();
440	ops.sort_by_key(\|(id, _)\| OpOrder::of(id));
441	ops
442	}
443
444	/// Renders the repository, judging causality by the operations it holds.
445	///
446	/// This is the ordinary path, the sequence being the whole history. Where a
447	/// caller holds the graph elsewhere -- a log covering more than this set --
448	/// use [`Sequence::render_with`].
449	pub fn render(&self)
450	-> Outcome<Repo>
451	{
452	self.render_with(&self.causality())
453	}
454
455	/// Renders the repository against a causal graph the caller holds.
456	///
457	/// Fails if the graph is not causally closed, if it does not hold every
458	/// operation the sequence does, or if the operation set names content or a
459	/// file it does not hold. Every render is checked for conservation before it
460	/// is returned, in a release build as much as a debug one, because the
461	/// structures the check needs are the ones the render is still holding.
462	pub fn render_with(&self, cause: &Causality<'_>)
463	-> Outcome<Repo>
464	{
465	let ops = self.in_op_order();
466	res!(self.check_described(cause));
467	res!(Self::check_parents(cause));
468	let atoms = res!(Atoms::build(&ops));
469	res!(Self::check_complete(&ops, &atoms));
470	let files = res!(Self::files(&ops));
471
472	// Where every byte was written, which is one of the two readings the
473	// cross-file classifier takes and is also what tells the overlap groups
474	// which file they are contending over. It is read off a layout with every
475	// move voided and no arbitration applied, so it costs one layout and no
476	// iteration: that layout is acyclic by construction.
477	let birth = res!(Self::birth_files(&ops, &res!(Dead::build(&ops)), &atoms));
478
479	// The render is one fixed point over two arbitrations. A cross-file cycle
480	// confines moves; an overlap group yields splices; and the two are the same
481	// kind of decision, so they are settled in one loop rather than in two that
482	// would each have to be right about the other's answer. Each pass arbitrates
483	// at most one cycle, and a pass that arbitrates one voids at least one move
484	// and never un-voids any, so it terminates.
485	//
486	// The yields are recomputed on every pass. Today they cannot change, being a
487	// function of the operation set and the causal graph alone, and confining a
488	// move changes neither; recomputing them is what keeps the loop correct if a
489	// later rule ever lets a confinement change what overlaps. The traffic runs
490	// the other way and is real: yielding changes the tombstones, the tombstones
491	// change what a trial layout shows, and a trial layout is what tells the
492	// cycle rule which file a block is in.
493	let mut voided: BTreeSet<OpId> = BTreeSet::new();
494	let mut confined: Vec<(OpId, OpId, OpId)> = Vec::new();
495	let mut won: Vec<OpId> = Vec::new();
496	let (claims, slots, order, walk, dead, yields) = loop {
497	let yields = res!(Self::yields(&ops, &birth, cause));
498	let dead = res!(Dead::build_without(&ops, &yields.buried));
499	let claims = res!(Claims::build_without(&ops, &voided));
500	let slots = res!(Slots::place_without(&ops, &voided));
501	match res!(self.arbitrate(
502	&ops, &slots, &claims, &dead, &atoms, &birth, &voided, cause))
503	{
504	Some(decision) => {
505	for (op, home, denied) in decision.losers {
506	if !voided.insert(op) {
507	return Err(err!(
508	"The move {} was confined twice, so the cross-file cycle \
509	rule is not making progress.", op;
510	Bug));
511	}
512	confined.push((op, home, denied));
513	}
514	if let Some(w) = decision.winner {
515	won.push(w);
516	}
517	},
518	None => {
519	let order = res!(slots.order(&claims));
520	let walk = res!(render::traverse(
521	&slots, &order, &claims, &dead, &atoms, render::Emit::Bytes));
522	break (claims, slots, order, walk, dead, yields);
523	},
524	}
525	};
526
527	// The association a wire field would have asserted, derived instead.
528	let mut index: BTreeMap<OpId, OpId> = BTreeMap::new();
529	for (i, slot) in slots.all().iter().enumerate() {
530	if let Some(f) = walk.owner[i] {
531	index.insert(slot.place, f);
532	}
533	}
534
535	let mut flags: Vec<Flag> = Vec::new();
536	for (op, sub, origin) in &order.demoted {
537	flags.push(Flag::Demoted { op: op, sub: sub, origin: *origin });
538	if let Some(f) = Self::crossed_file(&slots, &claims, &walk.owner, op, sub) {
539	flags.push(f);
540	}
541	}
542	for (op, sub, origin) in &order.dropped {
543	flags.push(Flag::Dropped { op: op, sub: sub, origin: *origin });
544	}
545	for (op, sub) in &walk.orphans {
546	flags.push(Flag::Orphaned { op: op, sub: sub });
547	}
548	for (op, home, denied) in &confined {
549	flags.push(Flag::Confined { op: op, home: home, denied: *denied });
550	}
551	for op in &won {
552	flags.push(Flag::Won { op: *op });
553	}
554	for (op, y) in &yields.map {
555	flags.push(Flag::Yielded {
556	op: *op,
557	to: y.to,
558	group: y.group.clone(),
559	through: y.through,
560	});
561	}
562	for (id, op) in &ops {
563	if !op.is_move() {
564	continue;
565	}
566	if let Some(f) = index.get(id) {
567	if !files.get(f).map(\|i\| i.live).unwrap_or(false) {
568	flags.push(Flag::MovedIntoDeleted { op: id, file: f });
569	}
570	}
571	}
572	flags.extend(res!(Self::torn(&ops, &claims, &voided, cause)));
573	flags.extend(res!(Self::overlaps(&ops, cause)));
574	flags.extend(res!(Self::stranded(&ops, &files, &yields.buried, cause)));
575	flags.extend(res!(Self::spliced_into_deleted(&ops, &files, &index, cause)));
576	flags.sort();
577	flags.dedup();
578
579	// Each file keeps the flags that concern it, and the repository keeps all
580	// of them; a flag naming an operation that reached no file is the
581	// repository's alone.
582	let mut per_file: BTreeMap<OpId, Vec<Flag>> = BTreeMap::new();
583	for flag in &flags {
584	for f in Self::flag_files(flag, &index) {
585	per_file.entry(f).or_default().push(flag.clone());
586	}
587	}
588
589	// Notes are read back off the provenance the walk produced, which is where
590	// every move the operation set holds has already happened.
591	let (mut per_file_notes, repo_notes) = render::notes(&ops, &walk.files);
592
593	let mut walk_files = walk.files;
594	let mut out: Vec<Rendered> = Vec::new();
595	let mut rendered = 0u64;
596	let mut withheld = 0u64;
597	for (id, info) in &files {
598	let (bytes, runs) = walk_files.remove(id).unwrap_or_default();
599	rendered += bytes.len() as u64;
600	if !info.live {
601	withheld += bytes.len() as u64;
602	}
603	let mut flags = per_file.remove(id).unwrap_or_default();
604	flags.dedup();
605	let notes = per_file_notes.remove(id).unwrap_or_default();
606	out.push(Rendered::new(
607	*id, info.path.clone(), info.mode, info.live, bytes, runs, flags, notes));
608	}
609
610	let stats = Stats {
611	ops: ops.len(),
612	files: files.len(),
613	atoms: atoms.count(),
614	atom_bytes: atoms.total(),
615	slots_placed: slots.placed(),
616	slots_divided: slots.len(),
617	claim_intervals: claims.intervals(),
618	dead_intervals: dead.intervals(),
619	notes: repo_notes.len(),
620	max_depth: walk.max_depth,
621	rendered,
622	withheld,
623	orphaned: walk.orphaned,
624	};
625	let repo = Repo::new(out, flags, repo_notes, index, stats);
626	// Checked here, in every build, because here is where it is nearly free:
627	// the atoms and the tombstones are the ones this render just used, and
628	// [`Sequence::check_conservation`] exists only for a caller holding a
629	// render it did not produce. Rebuilding them to ask the same question
630	// cost 5.51 s of a 20.2 s open, measured on a 44,628 operation history.
631	res!(Self::conserved(&repo, &atoms, &dead));
632	Ok(repo)
633	}
634
635	/// Checks that the render accounts for every byte the operation set created:
636	/// each is either rendered exactly once, somewhere in the repository, or
637	/// dead, or owned by a slot that reached no file at all.
638	///
639	/// The check is repository-wide because that is where it bites. A byte
640	/// rendered in two files at once is what a claim register scoped to one file
641	/// produces, and no per-file check would see it: each file would agree with
642	/// itself while the same bytes appeared in both. The render runs this under a
643	/// debug build; a caller wanting it in a release build calls it.
644	///
645	/// The tombstones are rebuilt under the same overlap arbitration the render
646	/// used, since a yielded insertion is dead rather than homeless and a check told
647	/// otherwise would report every yield as a byte gone missing. Causality is
648	/// judged by the sequence's own operations, so a caller who rendered against a
649	/// wider graph should check the render it holds rather than this.
650	///
651	/// A render this sequence produced has been checked already, by
652	/// [`Sequence::render_with`], and calling this on one rebuilds the atoms, the
653	/// tombstones, a whole trial layout and the overlap arbitration to reach the
654	/// same answer -- 5.51 s of a 20.2 s open, measured. What remains for this to
655	/// do is the case its name suggests: a repository assembled some other way,
656	/// or one deliberately damaged by a test.
657	pub fn check_conservation(&self, repo: &Repo)
658	-> Outcome<()>
659	{
660	let ops = self.in_op_order();
661	let cause = self.causality();
662	let atoms = res!(Atoms::build(&ops));
663	let birth = res!(Self::birth_files(&ops, &res!(Dead::build(&ops)), &atoms));
664	let yields = res!(Self::yields(&ops, &birth, &cause));
665	let dead = res!(Dead::build_without(&ops, &yields.buried));
666	Self::conserved(repo, &atoms, &dead)
667	}
668
669	/// Collects what the lifecycle operations say about each file, in op order.
670	fn files(ops: &[(OpId, &Op)])
671	-> Outcome<BTreeMap<OpId, FileInfo>>
672	{
673	let mut files: BTreeMap<OpId, FileInfo> = BTreeMap::new();
674	for (id, op) in ops {
675	match op {
676	Op::FileCreate { path } => {
677	files.insert(*id, FileInfo {
678	path: path.clone(),
679	mode: Mode::default(),
680	live: true,
681	});
682	},
683	// A forgotten file has no path to be laid out under and is dead
684	// from birth. It is still a file, so that a rename, a mode or a
685	// deletion naming it is complete rather than an error.
686	Op::Forgotten { placing: Placing::File } => {
687	files.insert(*id, FileInfo {
688	path: Vec::new(),
689	mode: Mode::default(),
690	live: false,
691	});
692	},
693	Op::FileRename { file, path } => {
694	match files.get_mut(file) {
695	Some(info) => info.path = path.clone(),
696	None => return Err(err!(
697	"The operation {} renames the file {}, which no operation \
698	in the set created; the set is not causally complete.",
699	id, file;
700	Invalid, Input, Missing)),
701	}
702	},
703	Op::FileMode { file, mode } => {
704	match files.get_mut(file) {
705	Some(info) => info.mode = *mode,
706	None => return Err(err!(
707	"The operation {} sets the mode of the file {}, which no \
708	operation in the set created; the set is not causally \
709	complete.", id, file;
710	Invalid, Input, Missing)),
711	}
712	},
713	Op::FileDelete { file } => {
714	match files.get_mut(file) {
715	Some(info) => info.live = false,
716	None => return Err(err!(
717	"The operation {} deletes the file {}, which no operation \
718	in the set created; the set is not causally complete.",
719	id, file;
720	Invalid, Input, Missing)),
721	}
722	},
723	_ => (),
724	}
725	}
726	Ok(files)
727	}
728
729	/// Arbitrates the first cross-file cycle the anchor graph holds, if it holds
730	/// one, and returns what it decided.
731	///
732	/// Every cycle is asked in turn and the first that decides anything is the
733	/// answer, the caller voiding what it names and rendering again. A cycle inside
734	/// one file decides nothing and falls through to demotion, which is where it
735	/// has always been settled.
736	#[allow(clippy::too_many_arguments)]
737	fn arbitrate(
738	&self,
739	ops: &[(OpId, &Op)],
740	slots: &Slots,
741	claims: &Claims,
742	dead: &Dead,
743	atoms: &Atoms,
744	birth: &BTreeMap<OpId, OpId>,
745	voided: &BTreeSet<OpId>,
746	cause: &Causality<'_>,
747	)
748	-> Outcome<Option<Decision>>
749	{
750	let arbiter = Arbiter { ops, dead, atoms, birth, cause };
751	for cycle in res!(slots.cycles(claims)) {
752	if let Some(decision) = res!(arbiter.judge(&cycle, slots, voided)) {
753	return Ok(Some(decision));
754	}
755	}
756	Ok(None)
757	}
758
759	/// The file every atom was written into.
760	///
761	/// Read off a layout with every move voided, so that the answer is where the
762	/// content would sit if nothing had ever been moved, which is what "the file
763	/// its origin names" means. That layout is always acyclic -- an origin names
764	/// content its author had already seen, so with no claims in play every edge
765	/// runs strictly downwards in op order -- so it costs one layout and no
766	/// iteration.
767	fn birth_files(ops: &[(OpId, &Op)], dead: &Dead, atoms: &Atoms)
768	-> Outcome<BTreeMap<OpId, OpId>>
769	{
770	let all: BTreeSet<OpId> = ops.iter()
771	.filter(\|(_, op)\| op.is_move())
772	.map(\|(id, _)\| *id)
773	.collect();
774	let laid = res!(Self::layout(ops, dead, atoms, &all));
775	let mut birth: BTreeMap<OpId, OpId> = BTreeMap::new();
776	for (i, slot) in laid.slots.all().iter().enumerate() {
777	// The slot the creating splice placed, which is where the content was
778	// written; a file's seed names the file itself.
779	if slot.place != slot.claim.op() {
780	continue;
781	}
782	if let Some(f) = laid.owner.get(i).copied().flatten() {
783	birth.insert(slot.claim.op(), f);
784	}
785	}
786	Ok(birth)
787	}
788
789	/// Lays the repository out with a set of moves voided, keeping enough of the
790	/// result to ask which file any byte sits in.
791	fn layout(
792	ops: &[(OpId, &Op)],
793	dead: &Dead,
794	atoms: &Atoms,
795	voided: &BTreeSet<OpId>,
796	)
797	-> Outcome<Layout>
798	{
799	let claims = res!(Claims::build_without(ops, voided));
800	let slots = res!(Slots::place_without(ops, voided));
801	let order = res!(slots.order(&claims));
802	// Only `owner` is kept below, so the content is not laid out at all.
803	let walk = res!(render::traverse(
804	&slots, &order, &claims, dead, atoms, render::Emit::OwnersOnly));
805	Ok(Layout { slots, claims, owner: walk.owner })
806	}
807
808	/// Raises a cross-file flag where breaking a cycle left a placement holding
809	/// content that was written into one file and renders in another.
810	///
811	/// The comparison is between where the content was written and where the
812	/// demoted placement put it, not between the two ends of the demoted origin,
813	/// which a cycle drawn tight around one gap would report nothing about.
814	///
815	/// Every demotion this sees is now inside one file, a cross-file cycle having
816	/// been arbitrated before the order was asked for. What still trips the flag is
817	/// a demoted placement whose content had legitimately changed files earlier,
818	/// and the flag is then telling the truth about the two files.
819	fn crossed_file(
820	slots: &Slots,
821	claims: &Claims,
822	owner: &[Option<OpId>],
823	op: OpId,
824	sub: u64,
825	)
826	-> Option<Flag>
827	{
828	let i = slots.find(&op, sub)?;
829	let slot = slots.get(i).ok()?;
830	// The slot placed by the splice that created this content, which is where
831	// the content was written and is where it would still be but for a move.
832	let born = ContentId::new(slot.claim.op(), slot.claim.from());
833	let home = slots.owner_slot(&born, claims, true).ok()?;
834	let from = (*owner.get(home)?)?;
835	let to = (*owner.get(i)?)?;
836	if from == to {
837	return None;
838	}
839	Some(Flag::CrossedFile { op, sub, from, to })
840	}
841
842	/// The files a flag concerns, so that each file keeps its own.
843	fn flag_files(flag: &Flag, index: &BTreeMap<OpId, OpId>) -> Vec<OpId> {
844	let mut out: Vec<OpId> = Vec::new();
845	match flag {
846	Flag::Overlap { ops, .. } => {
847	for id in ops {
848	if let Some(f) = index.get(id) {
849	out.push(*f);
850	}
851	}
852	},
853	Flag::CrossedFile { from, to, .. } => {
854	out.push(*from);
855	out.push(*to);
856	},
857	Flag::Confined { home, denied, .. } => {
858	out.push(*home);
859	out.push(*denied);
860	},
861	Flag::MovedIntoDeleted { file, .. } => out.push(*file),
862	Flag::Stranded { op, by } => {
863	for id in [op, by] {
864	if let Some(f) = index.get(id) {
865	out.push(*f);
866	}
867	}
868	},
869	Flag::SplicedIntoDeleted { file, .. } => out.push(*file),
870	// The yielder's file and the prevailing operation's, by the Stranded
871	// route, so that both authors are told where they are looking. The rest
872	// of the group is in the flag and is one lookup away; spraying the flag
873	// over every member's file would put a five-party collision into five
874	// files and tell nobody anything they could act on.
875	Flag::Yielded { op, to, .. } => {
876	for id in [op, to] {
877	if let Some(f) = index.get(id) {
878	out.push(*f);
879	}
880	}
881	},
882	other => {
883	if let Some(id) = other.op() {
884	if let Some(f) = index.get(&id) {
885	out.push(*f);
886	}
887	}
888	},
889	}
890	out.sort();
891	out.dedup();
892	out
893	}
894
895	/// Checks that the graph describes every operation the sequence holds.
896	fn check_described(&self, cause: &Causality<'_>)
897	-> Outcome<()>
898	{
899	for id in self.ops.keys() {
900	if !cause.contains(id) {
901	return Err(err!(
902	"The causal graph does not hold the operation {}, which the \
903	sequence does, so it cannot judge what that operation was \
904	written against.", id;
905	Invalid, Input, Missing));
906	}
907	}
908	Ok(())
909	}
910
911	/// Checks that every operation an operation was written against is present.
912	///
913	/// This is the causal precondition proper, read off the parents rather than
914	/// guessed at from the content. An operation whose parent is absent has been
915	/// delivered ahead of history it depends on, and no amount of anchor
916	/// resolution can make up the difference.
917	fn check_parents(cause: &Causality<'_>)
918	-> Outcome<()>
919	{
920	if let Some((id, missing)) = cause.gap() {
921	return Err(err!(
922	"The operation {} was written against {}, which the operation set \
923	does not hold; the set is not causally complete.", id, missing;
924	Invalid, Input, Missing));
925	}
926	Ok(())
927	}
928
929	/// Checks that every content identifier an operation names exists.
930	///
931	/// A file's origin anchor is one such identifier, so an operation anchored at
932	/// the start of a file the set does not hold is refused here along with
933	/// everything else it might have named.
934	///
935	/// The content a note is about is named here too, although the note claims
936	/// none of it. A note whose subject has not arrived cannot be resolved, and
937	/// resolving it to nothing would be indistinguishable from a note on content
938	/// that has been deleted, which is a different fact about the repository.
939	fn check_complete(ops: &[(OpId, &Op)], atoms: &Atoms)
940	-> Outcome<()>
941	{
942	for (id, op) in ops {
943	for r in op.regions().iter().chain(op.note_on()) {
944	if r.to() > atoms.run_len(&r.op()) {
945	return Err(err!(
946	"The operation {} names the content {}, which the operation \
947	set does not hold; the set is not causally complete.", id, r;
948	Invalid, Input, Missing));
949	}
950	}
951	let (left, right) = op.origins();
952	for a in [left, right].into_iter().flatten() {
953	if a.content.off >= atoms.run_len(&a.content.op) {
954	return Err(err!(
955	"The operation {} is anchored {}, which the operation set \
956	does not hold; the set is not causally complete.", id, a;
957	Invalid, Input, Missing));
958	}
959	}
960	}
961	Ok(())
962	}
963
964	/// Finds the moves whose source was taken from them by a concurrent move.
965	///
966	/// The claim register alone cannot tell a race from a sequence: a move
967	/// superseded on purpose, by a later move of the same content, looks exactly
968	/// like one that lost a race, because in both cases the register names
969	/// somebody else. The parents say which it was, and only a concurrent claim
970	/// tears. An author who moved a block and then moved it again is owed no flag,
971	/// and a flag they cannot act on is noise that hides the ones they can.
972	///
973	/// A move confined by the cross-file cycle rule owns nothing either, and would
974	/// look torn to a register that could not tell why. It is told
975	/// [`Flag::Confined`] instead: the two flags name different events, and an
976	/// author is owed the one that happened.
977	fn torn(
978	ops: &[(OpId, &Op)],
979	claims: &Claims,
980	voided: &BTreeSet<OpId>,
981	cause: &Causality<'_>,
982	)
983	-> Outcome<Vec<Flag>>
984	{
985	let mut out: Vec<Flag> = Vec::new();
986	for (id, op) in ops {
987	if !op.is_move() \|\| voided.contains(id) {
988	continue;
989	}
990	let mut lost: Vec<ContentRange> = Vec::new();
991	for r in op.regions() {
992	for (span, holder) in claims.runs(r) {
993	if holder == *id \|\| !cause.concurrent(&holder, id) {
994	continue;
995	}
996	let gone = res!(ContentRange::new(r.op(), span.start, span.end));
997	match lost.last_mut() {
998	Some(last) if last.op() == gone.op() && last.to() == gone.from()
999	=> res!(last.set_to(gone.to())),
1000	_ => lost.push(gone),
1001	}
1002	}
1003	}
1004	if !lost.is_empty() {
1005	out.push(Flag::Torn { op: *id, lost });
1006	}
1007	}
1008	Ok(out)
1009	}
1010
1011	/// Finds the pairs of concurrent operations that named the same content.
1012	///
1013	/// A sweep over the named runs, atom by atom: two operations overlap when one
1014	/// starts before another ends. Origins are not counted, because an origin
1015	/// names a gap rather than a claim on content, and two insertions at one gap
1016	/// are ordered rather than in conflict.
1017	///
1018	/// A pair that overlaps is then asked of the parents graph whether it was
1019	/// concurrent, and only a concurrent pair is flagged. An author who deleted a
1020	/// run they could already see was not in conflict with whoever wrote it, and
1021	/// saying so would make the flag noise. The concurrency test costs a walk of
1022	/// the graph per overlapping pair, and overlapping pairs are rare, so nothing
1023	/// is paid for the histories that have no conflict in them.
1024	fn overlaps(ops: &[(OpId, &Op)], cause: &Causality<'_>)
1025	-> Outcome<Vec<Flag>>
1026	{
1027	let mut named: Vec<(ContentRange, OpId)> = Vec::new();
1028	for (id, op) in ops {
1029	for r in op.regions() {
1030	if !r.is_empty() {
1031	named.push((r, id));
1032	}
1033	}
1034	}
1035	named.sort_by_key(\|(r, id)\| (r.op(), r.from(), r.to(), *id));
1036	let mut out: Vec<Flag> = Vec::new();
1037	// Runs still open at the current position, oldest first.
1038	let mut open: Vec<(ContentRange, OpId)> = Vec::new();
1039	for (r, id) in named {
1040	open.retain(\|(o, _)\| o.op() == r.op() && o.to() > r.from());
1041	for (o, other) in &open {
1042	if *other == id {
1043	continue;
1044	}
1045	if !cause.concurrent(other, &id) {
1046	continue;
1047	}
1048	if let Some(region) = o.intersection(&r) {
1049	let mut pair = vec![*other, id];
1050	pair.sort();
1051	out.push(Flag::Overlap { ops: pair, region });
1052	}
1053	}
1054	open.push((r, id));
1055	}
1056	Ok(out)
1057	}
1058
1059	/// Decides which splices yield, from the operation set, the causal graph, and
1060	/// the file each byte was written into.
1061	///
1062	/// The rule. Concurrent splices whose named content intersects form a graph,
1063	/// one edge per pair [`Sequence::overlaps`] flags, and its connected components
1064	/// are the arbitration groups; components contending over the same files by the
1065	/// same set of replicas are taken together. The member highest in op order
1066	/// prevails and every member concurrent with it yields, its removals not burying
1067	/// and its insertion buried whole. A splice anchored wholly inside a buried
1068	/// insertion yields too.
1069	///
1070	/// Why the component and not the pair. Arbitrating the intersection alone
1071	/// says nothing about either author's insertion, which is where the unreadable
1072	/// text comes from; arbitrating the whole file would void the work of somebody
1073	/// who was not contending. The component is the smallest unit that leaves the
1074	/// contended region reading as whole hunks. The same-contenders merge is what
1075	/// stops two components of one file being won by different replicas, which at
1076	/// two parties -- the case a small team hits -- is the whole of the fix.
1077	///
1078	/// The causal exemption. A member in the winner's causal past does not
1079	/// yield. It is not decoration: an author whose capture emitted two hunks
1080	/// authored the second with the first as its parent, so without the exemption a
1081	/// winner would void its own other hunk. The price is that the region is a
1082	/// promise of whole hunks rather than a promise of one author, since a third
1083	/// party who synced with one side of a collision and not the other joins the
1084	/// group as its maximum and leaves two authors' hunks composed.
1085	///
1086	/// Which file a component is in is read off the birth layout, where every
1087	/// byte was written. A component whose members named content born in more than
1088	/// one file has that whole set as its key and merges only with a component whose
1089	/// key matches, which is the per-file restriction stated so that it means
1090	/// something in a repository rather than in a single document.
1091	fn yields(
1092	ops: &[(OpId, &Op)],
1093	birth: &BTreeMap<OpId, OpId>,
1094	cause: &Causality<'_>,
1095	)
1096	-> Outcome<Yields>
1097	{
1098	// The splices, which is what arbitration reaches. A move already has two
1099	// arbitration rules of its own -- tearing, and the cross-file cycle -- and a
1100	// third interacting with the same fixed point is unbounded work for a case
1101	// nobody has yet observed.
1102	let sp: Vec<(OpId, &Op)> = ops.iter()
1103	.filter(\|(_, op)\| matches!(op, Op::Splice { .. }))
1104	.copied()
1105	.collect();
1106
1107	// The overlap graph, by the sweep `overlaps` uses: sort every named run by
1108	// atom and offset, and a run still open when another begins intersects it.
1109	let mut named: Vec<(ContentRange, usize)> = Vec::new();
1110	for (i, (_, op)) in sp.iter().enumerate() {
1111	for r in op.regions() {
1112	if !r.is_empty() {
1113	named.push((*r, i));
1114	}
1115	}
1116	}
1117	named.sort_by_key(\|(r, i)\| (r.op(), r.from(), r.to(), sp[*i].0));
1118	let mut up: Vec<usize> = (0..sp.len()).collect();
1119	let mut met: BTreeSet<usize> = BTreeSet::new();
1120	let mut open: Vec<(ContentRange, usize)> = Vec::new();
1121	for (r, i) in named {
1122	open.retain(\|(o, _)\| o.op() == r.op() && o.to() > r.from());
1123	for (_, j) in &open {
1124	if j == i \|\| !cause.concurrent(&sp[j].0, &sp[i].0) {
1125	continue;
1126	}
1127	met.insert(i);
1128	met.insert(*j);
1129	join(&mut up, i, *j);
1130	}
1131	open.push((r, i));
1132	}
1133	let mut out = Yields::default();
1134	if met.is_empty() {
1135	return Ok(out);
1136	}
1137
1138	// The connected components, and then the same-contenders merge over them.
1139	let mut comps: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
1140	for i in met {
1141	let root = find(&mut up, i);
1142	comps.entry(root).or_default().push(i);
1143	}
1144	let mut groups: BTreeMap<(BTreeSet<ReplicaId>, BTreeSet<OpId>), Vec<usize>>
1145	= BTreeMap::new();
1146	for members in comps.values() {
1147	let mut reps: BTreeSet<ReplicaId> = BTreeSet::new();
1148	let mut over: BTreeSet<OpId> = BTreeSet::new();
1149	for i in members {
1150	reps.insert(sp[*i].0.replica);
1151	for r in sp[*i].1.regions() {
1152	if let Some(f) = birth.get(&r.op()) {
1153	over.insert(*f);
1154	}
1155	}
1156	}
1157	groups.entry((reps, over)).or_default().extend(members.iter().copied());
1158	}
1159
1160	// The op-order maximum prevails; every member concurrent with it yields.
1161	for members in groups.values_mut() {
1162	members.sort_by_key(\|i\| OpOrder::of(&sp[*i].0));
1163	let group: Vec<OpId> = members.iter().map(\|i\| sp[*i].0).collect();
1164	let winner = match group.last() {
1165	Some(w) => *w,
1166	None => return Err(err!("An overlap group with no members."; Bug)),
1167	};
1168	for id in &group {
1169	if cause.concurrent(&winner, id) {
1170	out.map.insert(*id, Yield {
1171	to: winner,
1172	group: group.clone(),
1173	through: None,
1174	});
1175	}
1176	}
1177	}
1178
1179	// Yielding is transitive. A splice whose insertion is anchored wholly within
1180	// an insertion that is buried is buried too: left where it is, it renders as
1181	// a fragment at a dead site, and no flag fires for it, because no concurrent
1182	// operation deleted anything. The winner cannot be reached this way -- to
1183	// anchor inside a buried insertion is to have seen it, and everything buried
1184	// is concurrent with the winner -- so the closure cannot bury a whole group.
1185	let mut inserted: BTreeSet<OpId> = BTreeSet::new();
1186	for (id, op) in ops {
1187	if let Op::Splice { insert, .. } = op {
1188	if !insert.is_empty() {
1189	inserted.insert(*id);
1190	}
1191	}
1192	}
1193	loop {
1194	let buried: BTreeSet<OpId> = out.map.keys()
1195	.copied()
1196	.filter(\|o\| inserted.contains(o))
1197	.collect();
1198	let inside = \|a: &Option<crate::id::Anchor>\| -> Option<OpId> {
1199	let host = a.as_ref()?.content.op;
1200	buried.contains(&host).then_some(host)
1201	};
1202	let mut added = false;
1203	for (id, op) in ops {
1204	if out.map.contains_key(id) \|\| !matches!(op, Op::Splice { .. }) {
1205	continue;
1206	}
1207	let (l, r) = op.origins();
1208	let host = match (inside(&l), inside(&r)) {
1209	(Some(h), Some(_)) => h,
1210	_ => continue,
1211	};
1212	let parent = match out.map.get(&host) {
1213	Some(y) => y.clone(),
1214	None => continue,
1215	};
1216	out.map.insert(*id, Yield {
1217	to: parent.to,
1218	group: parent.group,
1219	through: Some(host),
1220	});
1221	added = true;
1222	}
1223	if !added {
1224	break;
1225	}
1226	}
1227	out.buried = out.map.keys().copied().collect();
1228	Ok(out)
1229	}
1230
1231	/// Finds the splices whose insertion anchored into content a concurrent
1232	/// operation deleted, so that the inserted bytes render at a deletion site
1233	/// rather than inside the context their author wrote them into.
1234	///
1235	/// The context of an insertion is the content its origins name; a file's
1236	/// origin anchor names no content a splice can remove, so it is not context.
1237	/// The flag fires only where every contextual neighbour is dead -- an
1238	/// insertion with a living neighbour renders beside it, where its author put
1239	/// it -- and only a concurrent deleter is named. A deletion causally
1240	/// ordered against the splice, either way round, was a decision made in
1241	/// knowledge of the other operation and raises nothing; this is the same
1242	/// distinction [`Sequence::torn`] draws, for the same reason.
1243	///
1244	/// A splice that yielded an overlap arbitration is left out of both halves of
1245	/// the question, because the arbitration answered it first. Its own insertion is
1246	/// buried, so it renders nowhere at all and cannot render at a deletion site;
1247	/// and its removals do not bury, so they leave nobody's context dead. Reporting
1248	/// either would name an event the render did not produce.
1249	fn stranded(
1250	ops: &[(OpId, &Op)],
1251	files: &BTreeMap<OpId, FileInfo>,
1252	yielded: &BTreeSet<OpId>,
1253	cause: &Causality<'_>,
1254	)
1255	-> Outcome<Vec<Flag>>
1256	{
1257	// Every run a splice removed, with the splice that removed it. Only a
1258	// splice kills bytes: a move relocates them, and an anchor follows.
1259	let mut removed: BTreeMap<OpId, Vec<(Range<u64>, OpId)>> = BTreeMap::new();
1260	for (id, op) in ops {
1261	if yielded.contains(id) {
1262	continue;
1263	}
1264	if let Op::Splice { remove, .. } = op {
1265	for r in remove {
1266	if !r.is_empty() {
1267	removed.entry(r.op()).or_default().push((r.offsets(), *id));
1268	}
1269	}
1270	}
1271	}
1272	let mut out: Vec<Flag> = Vec::new();
1273	for (id, op) in ops {
1274	if yielded.contains(id) {
1275	continue;
1276	}
1277	let (left, right) = match op {
1278	Op::Splice { left, right, insert, .. } if !insert.is_empty()
1279	=> (left, right),
1280	_ => continue,
1281	};
1282	// The neighbours the insertion was written beside. An absent origin
1283	// is the edge of the file, and a file's origin anchor is the same
1284	// edge spelled as content; neither is context that can die.
1285	let mut ctx: Vec<ContentId> = Vec::new();
1286	for a in [left, right].into_iter().flatten() {
1287	if !files.contains_key(&a.content.op) {
1288	ctx.push(a.content);
1289	}
1290	}
1291	if ctx.is_empty() {
1292	continue;
1293	}
1294	let mut deleters: Vec<OpId> = Vec::new();
1295	let mut all_dead = true;
1296	for c in &ctx {
1297	let mut dead_here = false;
1298	if let Some(runs) = removed.get(&c.op) {
1299	for (span, by) in runs {
1300	if span.contains(&c.off) {
1301	dead_here = true;
1302	if by != id && cause.concurrent(by, id) {
1303	deleters.push(*by);
1304	}
1305	}
1306	}
1307	}
1308	if !dead_here {
1309	all_dead = false;
1310	break;
1311	}
1312	}
1313	if !all_dead {
1314	continue;
1315	}
1316	deleters.sort();
1317	deleters.dedup();
1318	for by in deleters {
1319	out.push(Flag::Stranded { op: *id, by });
1320	}
1321	}
1322	Ok(out)
1323	}
1324
1325	/// Finds the splices that placed content in a file a concurrent
1326	/// [`Op::FileDelete`] retired.
1327	///
1328	/// Only the race is flagged. Every edit ever made goes dark when its file is
1329	/// deliberately deleted, and a deleter who could see the edit chose to delete
1330	/// it, exactly as an editor who could see the deletion chose to write into a
1331	/// dead file; neither is owed a flag, and the parents say which happened.
1332	/// This is narrower than [`Flag::MovedIntoDeleted`], which fires however move
1333	/// and deletion were ordered, because a move actively relocates content into
1334	/// the dead file rather than being overtaken in place.
1335	fn spliced_into_deleted(
1336	ops: &[(OpId, &Op)],
1337	files: &BTreeMap<OpId, FileInfo>,
1338	index: &BTreeMap<OpId, OpId>,
1339	cause: &Causality<'_>,
1340	)
1341	-> Outcome<Vec<Flag>>
1342	{
1343	// The deletions of each file. More than one is legal, and each is its
1344	// own author's decision, judged on its own parents.
1345	let mut dels: BTreeMap<OpId, Vec<OpId>> = BTreeMap::new();
1346	for (id, op) in ops {
1347	if let Op::FileDelete { file } = op {
1348	dels.entry(file).or_default().push(id);
1349	}
1350	}
1351	let mut out: Vec<Flag> = Vec::new();
1352	for (id, op) in ops {
1353	// A splice that removes without inserting places nothing, and loses
1354	// nothing to the deletion either: the file's death does strictly more
1355	// than the removal asked for.
1356	match op {
1357	Op::Splice { insert, .. } if !insert.is_empty() => (),
1358	_ => continue,
1359	}
1360	let f = match index.get(id) {
1361	Some(f) => *f,
1362	None => continue,
1363	};
1364	if files.get(&f).map(\|i\| i.live).unwrap_or(true) {
1365	continue;
1366	}
1367	for del in dels.get(&f).map(\|v\| v.as_slice()).unwrap_or(&[]) {
1368	if cause.concurrent(del, id) {
1369	out.push(Flag::SplicedIntoDeleted { op: id, file: f, del: del });
1370	}
1371	}
1372	}
1373	Ok(out)
1374	}
1375
1376	/// The conservation check proper, over the whole repository.
1377	fn conserved(repo: &Repo, atoms: &Atoms, dead: &Dead)
1378	-> Outcome<()>
1379	{
1380	let mut seen: BTreeMap<OpId, IntervalMap<()>> = BTreeMap::new();
1381	let mut emitted = 0u64;
1382	for file in repo.files() {
1383	for Run { content, .. } in file.runs() {
1384	if content.is_empty() {
1385	continue;
1386	}
1387	emitted += content.len();
1388	res!(seen.entry(content.op()).or_default().insert(content.offsets(), ()));
1389	}
1390	}
1391	let distinct: u64 = seen.values()
1392	.flat_map(\|m\| m.iter())
1393	.map(\|(iv, _)\| iv.end - iv.start)
1394	.sum();
1395	if distinct != emitted {
1396	return Err(err!(
1397	"Conservation failed: {} bytes were rendered across the repository \
1398	but only {} of them are distinct, so a byte was shown in two places.",
1399	emitted, distinct;
1400	Bug, Conflict));
1401	}
1402	let buried = dead.within(atoms);
1403	let orphaned = repo.stats().orphaned;
1404	if distinct + buried + orphaned != atoms.total() {
1405	return Err(err!(
1406	"Conservation failed: {} bytes rendered plus {} dead plus {} orphaned \
1407	against {} created.", distinct, buried, orphaned, atoms.total();
1408	Bug, Mismatch));
1409	}
1410	Ok(())
1411	}
1412	}
1413
1414
1415	/// What the overlap arbitration decided about one splice.
1416	#[derive(Clone, Debug, Eq, PartialEq)]
1417	struct Yield {
1418	to: OpId, // the op-order maximum, which prevailed
1419	group: Vec<OpId>, // ascending, so that the last of it is the winner
1420	through: Option<OpId>, // the buried insertion this splice sits inside
1421	}
1422
1423
1424	/// What the overlap arbitration decided about a whole operation set.
1425	#[derive(Clone, Debug, Default)]
1426	struct Yields {
1427	map: BTreeMap<OpId, Yield>, // every yielding splice, and what it yielded to
1428	buried: BTreeSet<OpId>, // the same, as the tombstones want it
1429	}
1430
1431
1432	/// The representative of a disjoint set, with the path halved on the way.
1433	fn find(up: &mut [usize], i: usize) -> usize {
1434	let mut r = i;
1435	while up[r] != r {
1436	r = up[r];
1437	}
1438	let mut c = i;
1439	while up[c] != c {
1440	let n = up[c];
1441	up[c] = r;
1442	c = n;
1443	}
1444	r
1445	}
1446
1447	fn join(up: &mut [usize], a: usize, b: usize) {
1448	let (ra, rb) = (find(up, a), find(up, b));
1449	if ra != rb {
1450	up[ra] = rb;
1451	}
1452	}
1453
1454
1455	/// One trial layout of the repository, kept only to be asked where things are.
1456	struct Layout {
1457	slots: Slots,
1458	claims: Claims, // the register they were laid out against
1459	owner: Vec<Option<OpId>>, // the file each slot ended up in
1460	}
1461
1462	impl Layout {
1463	/// The file a byte sits in, or `None` where no slot in this layout shows it.
1464	fn file_of(&self, cid: &ContentId) -> Option<OpId> {
1465	let i = match self.slots.owner_slot(cid, &self.claims, false) {
1466	Ok(i) => i,
1467	Err(_) => return None,
1468	};
1469	self.owner.get(i).copied().flatten()
1470	}
1471	}
1472
1473
1474	/// What arbitrating one cycle decided.
1475	struct Decision {
1476	winner: Option<OpId>, // where the arbitration names one
1477	losers: Vec<(OpId, OpId, OpId)>, // each with its home and denied files
1478	}
1479
1480
1481	/// What deciding a cycle takes: the operation set, the two structures a trial
1482	/// layout needs, where every byte was written, and what each author had seen.
1483	struct Arbiter<'a> {
1484	ops: &'a [(OpId, &'a Op)], // in op order
1485	dead: &'a Dead, // which a trial layout needs
1486	atoms: &'a Atoms, // likewise
1487	birth: &'a BTreeMap<OpId, OpId>, // the file every atom was written into
1488	cause: &'a Causality<'a>, // what tells a race from a sequence
1489	}
1490
1491	impl Arbiter<'_> {
1492
1493	/// Decides what to do with one cycle, or nothing.
1494	///
1495	/// Returns `None` where the rule declines, in which case the caller falls back
1496	/// to demotion: that is what happens to a cycle inside one file, to a cycle
1497	/// with no move in it to void, and to a cycle every one of whose members is
1498	/// informed.
1499	///
1500	/// The rule. A cycle in the anchor graph that crosses a file boundary is
1501	/// arbitrated as one concurrent group: the member highest in op order completes
1502	/// wholly, and every other member is voided back to its source and flagged. The
1503	/// design has already argued for this once, over the overlapping range move --
1504	/// one of your two moves happened and you were told which is easier to explain,
1505	/// and to undo, than half a block at each end of the repository.
1506	fn judge(
1507	&self,
1508	cycle: &[usize],
1509	slots: &Slots,
1510	voided: &BTreeSet<OpId>,
1511	)
1512	-> Outcome<Option<Decision>>
1513	{
1514	// The moves the cycle runs through, in op order. A splice in a cycle is not
1515	// voidable, since voiding an insertion would destroy content.
1516	let mut members: Vec<OpId> = Vec::new();
1517	for k in cycle {
1518	let place = res!(slots.get(*k)).place;
1519	if voided.contains(&place) \|\| members.contains(&place) {
1520	continue;
1521	}
1522	if self.op(&place).map(\|o\| o.is_move()).unwrap_or(false) {
1523	members.push(place);
1524	}
1525	}
1526	members.sort_by_key(OpOrder::of);
1527	if members.is_empty() {
1528	return Ok(None);
1529	}
1530
1531	// A member crosses a boundary when its content and its destination are in
1532	// different files, and that question is asked twice, of two repositories,
1533	// because neither answer alone is sound.
1534	//
1535	// Where the bytes would be if this cycle had not happened. One layout
1536	// with the cycle's members voided and nothing else. Asking which file a
1537	// member's content is in is circular while the cycle is unbroken -- the file
1538	// is read off the tree, and the tree is what the cycle is blocking -- and
1539	// voiding every member removes every edge of the cycle, so it lays out.
1540	//
1541	// Where the bytes were written. The birth layout, which is the only
1542	// reading that sees a cycle whose members supersede an earlier move of their
1543	// own: voiding such a cycle resurrects the superseded move, which carries
1544	// the content over the boundary itself, and both readings of the cycle then
1545	// come out inside one file when it is two.
1546	//
1547	// The rule is the union. Both failures are false negatives -- each reading
1548	// misses cycles, neither invents them -- and a false negative is a collapse
1549	// while a false positive is a voided move, which is flagged and reversible.
1550	let mut without: BTreeSet<OpId> = voided.clone();
1551	for m in &members {
1552	without.insert(*m);
1553	}
1554	let site = res!(Sequence::layout(self.ops, self.dead, self.atoms, &without));
1555
1556	let mut home: BTreeMap<OpId, OpId> = BTreeMap::new();
1557	let mut dest: BTreeMap<OpId, OpId> = BTreeMap::new();
1558	let mut cross: Vec<OpId> = Vec::new();
1559	for m in &members {
1560	let op = match self.op(m) {
1561	Some(o) => o,
1562	None => continue,
1563	};
1564	let (left, right) = op.origins();
1565	let anchor = match left.or(right) {
1566	Some(a) => a.content,
1567	None => continue,
1568	};
1569	let born_to = self.birth.get(&anchor.op).copied();
1570	let now_to = site.file_of(&anchor);
1571	let mut h: Option<OpId> = None;
1572	let mut differs = false;
1573	for r in op.regions() {
1574	if r.is_empty() {
1575	continue;
1576	}
1577	let first = ContentId::new(r.op(), r.from());
1578	let born_from = self.birth.get(&r.op()).copied();
1579	let now_from = site.file_of(&first);
1580	if h.is_none() {
1581	h = now_from.or(born_from);
1582	}
1583	if born_from.is_some() && born_from != born_to {
1584	differs = true;
1585	}
1586	if now_from.is_some() && now_to.is_some() && now_from != now_to {
1587	differs = true;
1588	}
1589	}
1590	let h = match h {
1591	Some(f) => f,
1592	None => continue,
1593	};
1594	let d = match now_to.or(born_to) {
1595	Some(f) => f,
1596	None => continue,
1597	};
1598	home.insert(*m, h);
1599	dest.insert(*m, d);
1600	if differs {
1601	cross.push(*m);
1602	}
1603	}
1604	if cross.is_empty() {
1605	return Ok(None);
1606	}
1607
1608	// A member that saw another member is informed rather than racing, and an
1609	// informed move is not voided for a race it did not have. This is the
1610	// distinction the torn flag had to learn: the claim register cannot tell a
1611	// race from a sequence, and the parents can.
1612	//
1613	// The exemption is for the causally last informed member only. Exempting
1614	// every member with another in its past is defeated by a chain of moves:
1615	// where a replica has made three in a row, each informed by the one before,
1616	// every member but the first is exempt, and where the first is not the one
1617	// that has to go the rule declines and the collapse happens anyway. A member
1618	// superseded by a later member of the same cycle is owed nothing, its own
1619	// author having moved on.
1620	let informed = \|m: &OpId\| {
1621	members.iter().any(\|n\| n != m && self.cause.reaches(m, n))
1622	&& !members.iter().any(\|n\| n != m && self.cause.reaches(n, m))
1623	};
1624
1625	// Where the cycle runs through only one move -- its other members being
1626	// splices, or the move anchoring inside its own source -- there is nothing
1627	// to arbitrate between, and a winner-takes-all rule that keeps its only
1628	// member would break no cycle at all. That move is confined instead, and the
1629	// cycle keeps no winner.
1630	let highest = members.iter().copied().max_by_key(OpOrder::of);
1631	let (winner, chosen): (Option<OpId>, Vec<OpId>) = if members.len() == 1 {
1632	(None, cross.iter().copied().filter(\|m\| !informed(m)).collect())
1633	} else {
1634	(highest, members.iter()
1635	.copied()
1636	.filter(\|m\| Some(*m) != highest && !informed(m))
1637	.collect())
1638	};
1639	let mut losers: Vec<(OpId, OpId, OpId)> = Vec::new();
1640	for m in chosen {
1641	let h = match home.get(&m) {
1642	Some(f) => *f,
1643	None => continue,
1644	};
1645	let d = dest.get(&m).copied().unwrap_or(h);
1646	losers.push((m, h, d));
1647	}
1648	if losers.is_empty() {
1649	return Ok(None);
1650	}
1651	Ok(Some(Decision { winner, losers }))
1652	}
1653
1654	fn op(&self, id: &OpId) -> Option<&Op> {
1655	self.ops.iter().find(\|(i, _)\| i == id).map(\|(_, op)\| *op)
1656	}
1657	}