oxedyne/fe2o3 — fe2o3

115 KiB, 878 runs

created by r1870400018:17511, 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 operation vocabulary: what a single unit of history can say.
2	//!
3	//! History here is a sequence of operations rather than a sequence of
4	//! snapshots. An operation states an intent -- create this file, put these
5	//! bytes beside those -- so the intent survives into the record and can be
6	//! reasoned about later, instead of being inferred back out of a diff.
7	//!
8	//! # Nothing names a position
9	//!
10	//! Every operation that speaks about bytes speaks about them by name. A splice
11	//! says which gap its bytes go in, by naming the content either side of that
12	//! gap, and says which content it removes, by naming that content; a move says
13	//! the same of the run it relocates. No operation carries a byte offset, a line
14	//! number or anything else that a concurrent edit could invalidate, which is
15	//! the property [`crate::seq`] is built on and the reason the two vocabularies
16	//! are now one.
17	//!
18	//! # Nothing names a file either
19	//!
20	//! A content operation names content and stops there. [`Op::Splice`] and
21	//! [`Op::Move`] carry no file, because the file a placement lands in is read off
22	//! the content it anchors to rather than asserted beside it: an author who
23	//! recorded a file could contradict the anchor, and the format would have no way
24	//! to say which of the two was right.
25	//!
26	//! What makes that total is the origin anchor. [`Op::FileCreate`] mints a
27	//! file, whose identity is the creating operation's own identity, and with it one
28	//! byte of content born dead -- [`crate::id::ContentId::origin`] -- so that an
29	//! empty file is not empty in identifier space. A splice into an empty file
30	//! anchors after that byte exactly as any other splice anchors after any other
31	//! byte, and the rule that replaces the file field is
32	//! [`Op::check_placement`]: an operation that places anything must carry at least
33	//! one origin, since that origin is what says where it lands.
34	//!
35	//! [`Op::FileRename`], [`Op::FileMode`] and [`Op::FileDelete`] name a file by
36	//! that identity. A path is metadata carried by the lifecycle operations and
37	//! nothing else, and it is bytes rather than a string, because a path is not
38	//! required to be UTF-8. A file's mode is metadata of the same kind, asserted by
39	//! naming the file rather than by naming its bytes, so it survives every edit
40	//! those bytes go on to have.
41	//!
42	//! # Naming content is not only for editing it
43	//!
44	//! [`Op::Note`] says something about content by naming it, and thereby inherits
45	//! the whole of the anchoring machinery: the note narrows when the content is
46	//! edited, travels when the content is moved, and crosses a file boundary when
47	//! the content does, none of which anything had to be written to make happen. A
48	//! note is not sequence content -- it mints no bytes and renders none -- so what
49	//! the render does with it is resolve it into spans; see
50	//! [`crate::seq::render::Note`].
51	//!
52	//! # Some operations are about the history and not about the bytes
53	//!
54	//! [`Op::Mark`] names a point in history; [`Op::Proposal`], [`Op::Said`] and
55	//! [`Op::Settled`] carry an argument about what the bytes ought to become; and
56	//! [`Op::Reverts`] says what a set of edits was written to undo. None of them
57	//! mints an atom, claims a byte or renders one, and the sequence keeps them for
58	//! the reason it keeps a note: the causal graph has to be whole.
59	//!
60	//! They are operations rather than records kept beside the repository because a
61	//! clone that arrives without them arrives without the reasons. A proposal held
62	//! in a forge's own store is readable only through that forge; a revert that
63	//! leaves no trace is an unexplained deletion by a stranger when it reaches
64	//! somebody else's machine, and the author of the work being undone has nothing
65	//! to read and nothing to be credited by.
66	//!
67	//! What is deliberately not here is a ballot. An operation is signed by its
68	//! author, so a vote written into the log would name its voter permanently and
69	//! irrevocably; tallies are published and voters are not, and that promise
70	//! cannot be kept by a format that records the votes.
71	//!
72	//! # Every operation carries its parents
73	//!
74	//! An operation records the frontier its author could see when they wrote it,
75	//! in [`Header::parents`]. That is what makes the history a graph rather than a
76	//! list: with it, [`crate::log::OpLog`] can say whether a set is causally
77	//! complete, and [`crate::seq`] can say whether two operations that touched the
78	//! same bytes were concurrent or merely consecutive. Parents live on the header
79	//! and not on the variants, because causality is a property of every operation
80	//! alike and duplicating it once per variant would let the copies drift.
81	//!
82	//! A time is not the same thing and is not on the header. Only the operations
83	//! that carry one have one, it is the author's own clock rather than a position
84	//! in the order, and nothing decides anything by it: see [`Op::Mark`].
85	//!
86	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
87	//! Anthropic Claude
88
89	use crate::id::{
90	varint_decode,
91	varint_encode,
92	Anchor,
93	ContentId,
94	ContentRange,
95	OpId,
96	Side,
97	};
98
99	use oxedyne_fe2o3_core::prelude::*;
100	use oxedyne_fe2o3_iop_hash::api::{
101	Hash,
102	Hasher,
103	};
104	use oxedyne_fe2o3_jdat::prelude::*;
105
106	use std::sync::Arc;
107
108
109	//// Operation wire codes.
110	pub const CODE_FILE_CREATE: u8 = 1;
111	pub const CODE_FILE_DELETE: u8 = 2;
112	pub const CODE_FILE_RENAME: u8 = 3;
113	pub const CODE_MARK: u8 = 4;
114	pub const CODE_SPLICE: u8 = 5;
115	pub const CODE_MOVE: u8 = 6;
116	pub const CODE_NOTE: u8 = 7;
117	pub const CODE_FILE_MODE: u8 = 8;
118	pub const CODE_MARK_TIMED: u8 = 9; // a mark carrying a body, a time, or both
119	pub const CODE_PROPOSAL: u8 = 10;
120	pub const CODE_SAID: u8 = 11;
121	pub const CODE_SETTLED: u8 = 12;
122	pub const CODE_REVERTS: u8 = 13;
123	pub const CODE_AMENDED: u8 = 14; // a proposal's author restating it
124	pub const CODE_FORGET: u8 = 15; // earlier operations losing their content
125	pub const CODE_FORGOTTEN: u8 = 16; // what stands where a forgotten one stood
126
127
128	/// The character beginning the name of an [`Op::Mark`] a tool wrote rather than
129	/// a person, and which a person's mark may not begin with.
130	///
131	/// One character is the whole of the convention, and it is here rather than in
132	/// whichever tool authors the marks because every reader of a history has to
133	/// apply it and they are not all the same program. A tool that names a point at
134	/// the end of every command writes a great many marks, and telling them apart by
135	/// name is what lets a reader be shown the handful somebody chose.
136	pub const AUTO_MARK_PREFIX: char = '@';
137
138	/// Is this the name of a mark a tool wrote rather than one a person chose?
139	///
140	/// Takes the name rather than the [`Op`], since a caller reading a reference
141	/// somebody typed has nothing else to hand it.
142	///
143	/// ```
144	/// use oxedyne_fe2o3_ore::op::{is_auto_mark, Op};
145	///
146	/// let op = Op::Mark {
147	/// name: String::from("@2026-08-17T04:12:09.482913Z"),
148	/// body: None,
149	/// time: Some(1_755_403_929),
150	/// };
151	/// assert!(match &op {
152	/// Op::Mark { name, .. } => is_auto_mark(name),
153	/// _ => false,
154	/// });
155	/// assert!(!is_auto_mark("release 1.0"));
156	/// ```
157	///
158	/// It says nothing about whether the name is a datetime, and deliberately so.
159	/// What a tool spells after the prefix is that tool's business and may differ
160	/// between them; what every reader has to agree on is which marks are somebody's
161	/// own, and that is one character.
162	pub fn is_auto_mark(name: &str) -> bool {
163	name.starts_with(AUTO_MARK_PREFIX)
164	}
165
166
167	/// What a mark's body calls the identity line the commit it was imported from was
168	/// authored under.
169	///
170	/// A trailer in git's own sense -- last line, `Key: value` -- so that a body
171	/// already ending in `Co-Authored-By:` lines gains it inside the block those lines
172	/// are in. Here rather than in the importer for the reason [`AUTO_MARK_PREFIX`] is
173	/// here: an importer writes it, a mirror reads it back to author the commit under
174	/// the name it arrived with, and a forge reads it to show a person the name and not
175	/// the bookkeeping. Three programs, one convention, and the day two of them spell
176	/// it differently is the day the forge and the mirror disagree about what a mark
177	/// says.
178	///
179	/// # What the value is
180	///
181	/// Git's whole author line, `Name <email> 1735089438 +0800`: the identity, the
182	/// moment and the zone offset the author's own clock was reading. Not the identity
183	/// alone. [`Op::Mark`] carries a time in UTC and no zone, so an offset survives an
184	/// import only here, and a mirror writing a commit back out reads it from here.
185	///
186	/// A reader showing this to a person shows the name, not the line. The moment
187	/// is bookkeeping, and a page that prints the value whole prints a timestamp in the
188	/// middle of an author's name. [`crate::fastexport::identity_in`] is that name and
189	/// [`crate::fastexport::split_identity_line`] is both halves; the two functions
190	/// below take the value as opaque bytes and neither looks at its shape, so the
191	/// split lives beside [`crate::fastexport::When`], whose format it is.
192	///
193	/// A reader does not write its own split. Where a name ends and a moment begins
194	/// is one rule with three readers, and the day two of them decide it differently is
195	/// the day this constant was moved here to prevent.
196	pub const AUTHOR_TRAILER: &str = "Ore-Author: ";
197
198	/// Adds the identity line a commit was authored under to the body its mark will
199	/// carry.
200	///
201	/// No blank line before it, so that the trailer joins whatever block ends the body
202	/// -- which is where git puts its own -- and taking exactly one line back off is
203	/// unambiguous however the body ended.
204	pub fn with_author(body: Option<&[u8]>, identity: &[u8]) -> Vec<u8> {
205	let mut out = body.unwrap_or_default().to_vec();
206	if !out.is_empty() && !out.ends_with(b"\n") {
207	out.push(b'\n');
208	}
209	out.extend_from_slice(AUTHOR_TRAILER.as_bytes());
210	out.extend_from_slice(identity);
211	out.push(b'\n');
212	out
213	}
214
215	/// Splits the identity line back off a mark's body, where it carries one.
216	///
217	/// # One line, and never a loop
218	///
219	/// A commit message may say anything, including a last line of its own beginning
220	/// `Ore-Author:`, and [`with_author`] writes the importer's trailer after
221	/// whatever was already there. So the importer's is always the last line and
222	/// exactly one line comes off. A reader that stripped until no trailer remained
223	/// would eat the person's line as well and author the commit under the name in it,
224	/// which is a round trip that silently rewrites history rather than reproducing it.
225	///
226	/// # What it cannot decide
227	///
228	/// A mark authored in Ore rather than imported, whose body's last line a person
229	/// typed as `Ore-Author: ...`, is indistinguishable from an imported one and is
230	/// split. Nothing in a mark says whether it was imported, and adding something
231	/// would be a discriminator in the history for the benefit of one importer. What a
232	/// caller loses is one line of a body, which for a mirror is a name it would have
233	/// derived anyway and for a reader is a line shown as an author instead of as
234	/// text.
235	///
236	/// The identity is bytes and is not checked: git says nothing about the encoding
237	/// of an identity line, and a caller that has to put it on a page decodes it there.
238	///
239	/// ```
240	/// use oxedyne_fe2o3_ore::op::{with_author, without_author};
241	///
242	/// let said = b"Tidy the parser.\n";
243	/// let line = b"Jason Hoogland <hoogland@gmail.com> 1735089438 +0800";
244	/// let carried = with_author(Some(said), line);
245	/// let (body, who) = without_author(&carried);
246	/// assert_eq!(body, said);
247	/// assert_eq!(who, Some(&line[..]));
248	///
249	/// // A commit message ending in a line of its own that looks like the trailer.
250	/// // One line comes off, and the person's line survives untouched.
251	/// let awkward = b"Fix it.\nOre-Author: Somebody Else <else@example.com>\n";
252	/// let carried = with_author(Some(awkward), b"Jason Hoogland <hoogland@gmail.com>");
253	/// let (body, who) = without_author(&carried);
254	/// assert_eq!(body, awkward);
255	/// assert_eq!(who, Some(&b"Jason Hoogland <hoogland@gmail.com>"[..]));
256	///
257	/// // A mark nobody imported carries no trailer and is handed back whole.
258	/// let (body, who) = without_author(b"Ready to cut.\n");
259	/// assert_eq!(body, b"Ready to cut.\n");
260	/// assert_eq!(who, None);
261	/// ```
262	pub fn without_author(body: &[u8]) -> (&[u8], Option<&[u8]>) {
263	// A body the importer wrote ends in the newline that terminates its trailer, so
264	// one that does not end in a newline cannot be carrying one.
265	let above = match body.strip_suffix(b"\n") {
266	Some(above) => above,
267	None => return (body, None),
268	};
269	let start = match above.iter().rposition(\|b\| *b == b'\n') {
270	Some(at) => at + 1,
271	None => 0,
272	};
273	match above[start..].strip_prefix(AUTHOR_TRAILER.as_bytes()) {
274	Some(identity) => (&body[..start], Some(identity)),
275	None => (body, None),
276	}
277	}
278
279
280	//// File mode wire codes.
281	pub const MODE_NORMAL: u8 = 0;
282	pub const MODE_EXECUTABLE: u8 = 1;
283	pub const MODE_SYMLINK: u8 = 2;
284
285
286	//// Proposal state wire codes.
287	pub const SETTLED_OPEN: u8 = 0;
288	pub const SETTLED_ACCEPTED: u8 = 1;
289	pub const SETTLED_DECLINED: u8 = 2;
290	pub const SETTLED_DONE: u8 = 3;
291
292
293	/// What a file is, over and above the bytes in it.
294	///
295	/// A three-value enum and not a number: a mode outside the set is not a state a
296	/// working copy can be in, and a reader should not have to guess what one would
297	/// mean. [`Mode::Normal`] is the default, and that is what makes the operation
298	/// additive -- a file no [`Op::FileMode`] ever named is a normal file, so every
299	/// history written before the operation existed means today what it meant
300	/// yesterday.
301	#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
302	pub enum Mode {
303	#[default]
304	Normal,
305	Executable,
306	Symlink, // whose bytes are the path it points at
307	}
308
309	impl Mode {
310	pub const fn code(&self) -> u8 {
311	match self {
312	Self::Normal => MODE_NORMAL,
313	Self::Executable => MODE_EXECUTABLE,
314	Self::Symlink => MODE_SYMLINK,
315	}
316	}
317
318	pub const fn name(&self) -> &'static str {
319	match self {
320	Self::Normal => "normal",
321	Self::Executable => "executable",
322	Self::Symlink => "symlink",
323	}
324	}
325
326	pub const fn is_normal(&self) -> bool {
327	matches!(self, Self::Normal)
328	}
329
330	pub const fn to_dat(&self) -> Dat {
331	Dat::U8(self.code())
332	}
333
334	pub fn from_dat(dat: &Dat)
335	-> Outcome<Self>
336	{
337	let code = match dat {
338	Dat::U8(c) => *c,
339	other => return Err(err!(
340	"A file mode expects Dat::U8, got {:?}.", other;
341	Decode, Input, Mismatch)),
342	};
343	match code {
344	MODE_NORMAL => Ok(Self::Normal),
345	MODE_EXECUTABLE => Ok(Self::Executable),
346	MODE_SYMLINK => Ok(Self::Symlink),
347	other => Err(err!(
348	"File mode {} is not one of {} for normal, {} for executable and {} \
349	for a symbolic link.",
350	other, MODE_NORMAL, MODE_EXECUTABLE, MODE_SYMLINK;
351	Decode, Input, Invalid)),
352	}
353	}
354	}
355
356	impl std::fmt::Display for Mode {
357	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
358	write!(f, "{}", self.name())
359	}
360	}
361
362
363	/// What became of a proposal. Four states and no workflow.
364	///
365	/// There is no transition table beside it, because a state is asserted rather
366	/// than stepped to: an author says what a proposal now is, and the assertion
367	/// stands until another one is written. [`Settled::Open`] is the default, so an
368	/// [`Op::Proposal`] that nothing has settled yet is open without anything having
369	/// had to say so.
370	#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
371	pub enum Settled {
372	#[default]
373	Open,
374	Accepted,
375	Declined,
376	Done, // agreed to and carried out
377	}
378
379	impl Settled {
380	pub const fn code(&self) -> u8 {
381	match self {
382	Self::Open => SETTLED_OPEN,
383	Self::Accepted => SETTLED_ACCEPTED,
384	Self::Declined => SETTLED_DECLINED,
385	Self::Done => SETTLED_DONE,
386	}
387	}
388
389	pub const fn name(&self) -> &'static str {
390	match self {
391	Self::Open => "open",
392	Self::Accepted => "accepted",
393	Self::Declined => "declined",
394	Self::Done => "done",
395	}
396	}
397
398	pub const fn is_open(&self) -> bool {
399	matches!(self, Self::Open)
400	}
401
402	pub const fn to_dat(&self) -> Dat {
403	Dat::U8(self.code())
404	}
405
406	pub fn from_dat(dat: &Dat)
407	-> Outcome<Self>
408	{
409	let code = match dat {
410	Dat::U8(c) => *c,
411	other => return Err(err!(
412	"A settled state expects Dat::U8, got {:?}.", other;
413	Decode, Input, Mismatch)),
414	};
415	match code {
416	SETTLED_OPEN => Ok(Self::Open),
417	SETTLED_ACCEPTED => Ok(Self::Accepted),
418	SETTLED_DECLINED => Ok(Self::Declined),
419	SETTLED_DONE => Ok(Self::Done),
420	other => Err(err!(
421	"Settled state {} is not one of {} for open, {} for accepted, {} for \
422	declined and {} for done.",
423	other, SETTLED_OPEN, SETTLED_ACCEPTED, SETTLED_DECLINED, SETTLED_DONE;
424	Decode, Input, Invalid)),
425	}
426	}
427	}
428
429	impl std::fmt::Display for Settled {
430	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
431	write!(f, "{}", self.name())
432	}
433	}
434
435
436	/// The one thing an operation's inverse needs that the operation does not say,
437	/// and which only the state it was written against holds.
438	///
439	/// An operation records an intent and not the state it displaced, so undoing the
440	/// three that assert a value has to read the value they replaced from somewhere.
441	/// That somewhere is a render at the operation's parents, which the engine does
442	/// not have and every caller does. This says which question to ask; asking it is
443	/// the caller's.
444	///
445	/// Rendering the operation set without the operation is not the way to answer
446	/// any of these, and cannot be made to work: removing an operation from the
447	/// middle of a history leaves anchors naming atoms nothing created, which
448	/// `Sequence::render_with` refuses rather than guesses at.
449	#[derive(Clone, Debug, Eq, PartialEq)]
450	pub enum Prior {
451	Path {
452	file: OpId,
453	},
454	Mode {
455	file: OpId,
456	},
457	// One gap per run, in the order the runs are named.
458	Place {
459	src: Vec<ContentRange>,
460	},
461	}
462
463	/// What undoing an operation amounts to, as far as the operation itself can say.
464	///
465	/// It is here rather than in whichever tool authors a revert for the reason
466	/// [`AUTO_MARK_PREFIX`] is here: more than one program will offer to undo an
467	/// operation, and two tables of what an inverse is would be two tables that
468	/// could disagree about a history they both write into.
469	///
470	/// The three fields are three different kinds of answer, and a caller that
471	/// serves only the first is a caller that silently half-undoes a splice:
472	///
473	/// - [`Undoing::written`] is the part the operation is enough for, exactly.
474	/// - [`Undoing::copies`] is content the operation killed, which comes back only
475	/// as a copy under a new identity, because nothing here un-buries: the
476	/// tombstone set is grow-only and is recomputed from the operation set on every
477	/// render. See [`Op::restoring`].
478	/// - [`Undoing::prior`] is a question for the state the operation was written
479	/// against.
480	#[derive(Clone, Debug, Default, Eq, PartialEq)]
481	pub struct Undoing {
482	pub written: Vec<Op>,
483	pub copies: Vec<ContentRange>, // one restoring splice per run
484	pub prior: Option<Prior>,
485	}
486
487	/// A single unit of history: one whole edit.
488	///
489	/// The vocabulary is an enum rather than a trait object, so a reader can
490	/// enumerate everything history is able to say and the compiler can insist that
491	/// every consumer handles all of it.
492	///
493	/// [`Op::Move`] is why the vocabulary needs more than a splice. A move is not a
494	/// delete plus an insert: it names the run it relocates by the identity of the
495	/// bytes themselves, so an edit made concurrently inside that run lands in the
496	/// run's new home rather than on a tombstone. Nothing in a move says where
497	/// anything is -- the source is content, the destination is an anchor -- and
498	/// since a splice says the same, the sequence structure in [`crate::seq`] can
499	/// resolve any two of them against each other however they happen to arrive, in
500	/// one file or across two.
501	/// What a forgotten operation still does to the render, once its content is gone.
502	///
503	/// Forgetting takes the bytes and leaves the shape. An insertion's shape is its
504	/// anchors, what it removed, and how many bytes it placed: with those kept, every
505	/// later edit anchored inside the forgotten text still resolves, against text
506	/// that is now buried whole. A file's creation still mints its origin anchor, so
507	/// a splice into it still has something to name, and the file is dead from
508	/// birth. Everything else -- a mark's words, a note's text, a proposal's body, a
509	/// rename's path -- has a shape that touches no byte, and is void.
510	#[derive(Clone, Debug, Eq, PartialEq)]
511	pub enum Placing {
512	Void,
513	File,
514	Splice {
515	left: Option<Anchor>,
516	right: Option<Anchor>,
517	remove: Vec<ContentRange>,
518	len: u64, // bytes the insertion placed, all of them buried
519	},
520	}
521
522	impl Placing {
523	pub const fn code(&self) -> u8 {
524	match self {
525	Self::Void => 0,
526	Self::File => 1,
527	Self::Splice { .. } => 2,
528	}
529	}
530
531	pub fn to_dat(&self) -> Dat {
532	match self {
533	Self::Void => Dat::List(vec![Dat::U8(0)]),
534	Self::File => Dat::List(vec![Dat::U8(1)]),
535	Self::Splice { left, right, remove, len } => Dat::List(vec![
536	Dat::U8(2),
537	Anchor::opt_to_dat(left),
538	Anchor::opt_to_dat(right),
539	Dat::List(remove.iter().map(\|r\| r.to_dat()).collect()),
540	Dat::U64(*len),
541	]),
542	}
543	}
544
545	pub fn from_dat(dat: &Dat)
546	-> Outcome<Self>
547	{
548	let v = match dat {
549	Dat::List(v) if !v.is_empty() => v,
550	other => return Err(err!(
551	"A Placing is a non-empty list, not {:?}.", other;
552	Decode, Input, Invalid)),
553	};
554	let code = match &v[0] {
555	Dat::U8(c) => *c,
556	other => return Err(err!(
557	"A Placing opens with its code as a U8, not {:?}.", other;
558	Decode, Input, Invalid)),
559	};
560	match code {
561	0 => {
562	res!(expect_len(v, 1, "Placing::Void"));
563	Ok(Self::Void)
564	},
565	1 => {
566	res!(expect_len(v, 1, "Placing::File"));
567	Ok(Self::File)
568	},
569	2 => {
570	res!(expect_len(v, 5, "Placing::Splice"));
571	Ok(Self::Splice {
572	left: res!(Anchor::opt_from_dat(&v[1])),
573	right: res!(Anchor::opt_from_dat(&v[2])),
574	remove: res!(as_ranges(&v[3], "Placing::Splice remove")),
575	len: res!(as_u64(&v[4], "Placing::Splice len")),
576	})
577	},
578	other => Err(err!(
579	"Placing code {} is not recognised.", other;
580	Decode, Input, Invalid)),
581	}
582	}
583	}
584
585	/// One operation a [`Op::Forget`] names, and the shape it keeps.
586	#[derive(Clone, Debug, Eq, PartialEq)]
587	pub struct Stub {
588	pub id: OpId,
589	pub placing: Placing,
590	}
591
592	impl Stub {
593	pub fn to_dat(&self) -> Dat {
594	Dat::List(vec![self.id.to_dat(), self.placing.to_dat()])
595	}
596
597	pub fn from_dat(dat: &Dat)
598	-> Outcome<Self>
599	{
600	let v = match dat {
601	Dat::List(v) if v.len() == 2 => v,
602	other => return Err(err!(
603	"A Stub is a list of an identifier and a placing, not {:?}.", other;
604	Decode, Input, Invalid)),
605	};
606	Ok(Self {
607	id: res!(OpId::from_dat(&v[0])),
608	placing: res!(Placing::from_dat(&v[1])),
609	})
610	}
611	}
612
613	#[derive(Clone, Debug, Eq, PartialEq)]
614	pub enum Op {
615	FileCreate {
616	path: Vec<u8>,
617	},
618	// A file's content is held back rather than destroyed, so whatever moved out
619	// of it before it went still renders where it went.
620	FileDelete {
621	file: OpId,
622	},
623	FileRename {
624	file: OpId,
625	path: Vec<u8>,
626	},
627	// A file no such operation names is normal, and two of these written
628	// concurrently settle the way two concurrent renames do: the later in
629	// operation order is the one the render reports.
630	FileMode {
631	file: OpId,
632	mode: Mode,
633	},
634	// Two wire spellings of the one variant, chosen by what it carries: see
635	// Op::code.
636	Mark {
637	name: String,
638	body: Option<Vec<u8>>,
639	time: Option<u64>, // unix epoch seconds, and it orders nothing
640	},
641	// The single primitive insertion, deletion and replacement all follow from:
642	// an insertion removes nothing, a deletion inserts nothing, a replacement
643	// does both at once.
644	//
645	// One buffer, three owners. `insert` is shared rather than owned outright
646	// because the log's record, the sequence's cloned `Applied` and the
647	// `crate::seq::atom::Atoms` entry all want the same bytes: three copies cost
648	// 7.63 kB of resident memory per operation on a real 44,628-operation
649	// history. The FIXED structures come to about 344 bytes of that; the rest is
650	// not all content, and saying so was an error in an earlier draft of this
651	// comment -- the remainder also holds envelope payloads, the segment buffer
652	// read whole, and BTreeMap nodes that split badly under ascending keys.
653	// Sharing took the figure to 5.79 kB, so `Sequence::apply_record`'s clone of
654	// an operation is a refcount bump and an atom is a handle. The wire form is
655	// untouched -- `to_dat` hands `Dat::BU64` the same byte sequence whatever
656	// owns it -- which had to be true, since a format that moved here would make
657	// every existing store unreadable.
658	Splice {
659	left: Option<Anchor>, // binds after a byte
660	right: Option<Anchor>, // binds before a byte
661	remove: Vec<ContentRange>,
662	insert: Arc<[u8]>, // shared, so a clone copies no bytes
663	},
664	Move {
665	src: Vec<ContentRange>, // in the order it lands in
666	left: Option<Anchor>,
667	right: Option<Anchor>,
668	},
669	Note {
670	on: Vec<ContentRange>,
671	text: Vec<u8>, // not this crate's to decode
672	},
673	Proposal {
674	title: String,
675	body: Vec<u8>,
676	voice: String, // the forge name the author wrote under
677	time: u64, // unix epoch seconds
678	},
679	Said {
680	on: OpId, // the proposal spoken about
681	text: Vec<u8>,
682	voice: String,
683	time: u64,
684	},
685	// Later in operation order wins, as with a rename.
686	Settled {
687	on: OpId,
688	state: Settled,
689	mark: Option<OpId>, // an identifier, never a mark's name
690	time: u64,
691	},
692	// A proposal's author saying it again, better. The opening operation is never
693	// altered and the earlier statements stay in the log, so what a reader sees is
694	// the latest amendment its author wrote and the record of every one before it.
695	// Whether an amendment counts is a question about its author, and the answer is
696	// the same on every replica: it is folded where `voice` is the voice that
697	// opened the proposal, and passed over otherwise. That comparison is against
698	// the opening operation alone, so it does not depend on what else the log holds
699	// or on the order a reader walks it.
700	Amended {
701	on: OpId, // the proposal being restated
702	title: String,
703	body: Vec<u8>,
704	voice: String,
705	time: u64,
706	},
707	Reverts {
708	undone: Vec<OpId>, // ascending, without repetition, never empty
709	},
710	// Earlier operations losing their content and keeping their shape. Ore
711	// reconstructs every state from the operations, which is what makes merging
712	// tractable, and it was never a promise to keep everything: history is the
713	// author's data. What this records is the act, so that every replica forgets
714	// the same things, and so that the log always says that it forgot. The
715	// stubs are the authority on what shape each forgotten operation keeps; a
716	// replica still holding the original bytes and one holding only a
717	// `Forgotten` render the same, because both read the shape from here.
718	Forget {
719	of: Vec<Stub>, // ascending by identifier, without repetition, never empty
720	reason: Vec<u8>, // not this crate's to decode; may be empty
721	time: u64, // unix epoch seconds, and it orders nothing
722	},
723	// What stands under a forgotten operation's own header once its bytes are
724	// gone from the store. Written by a repack in the original's place, never
725	// authored; the `Forget` naming it is what vouches for it.
726	Forgotten {
727	placing: Placing,
728	},
729	}
730
731	impl Op {
732	/// A mark answers with the code it is written at, which is a function of
733	/// what it carries rather than of the variant: a mark with neither a body
734	/// nor a time is [`CODE_MARK`] with the two elements it has always had, so
735	/// every mark already signed still verifies, and a mark with either is
736	/// [`CODE_MARK_TIMED`] with four. That is what
737	/// [`crate::segment::highest_code`] reads, so a bodyless, timeless mark goes
738	/// into a segment of any version this crate reads, and a mark carrying
739	/// either does not go into one written before the fields existed.
740	pub fn code(&self) -> u8 {
741	match self {
742	Self::FileCreate { .. } => CODE_FILE_CREATE,
743	Self::FileDelete { .. } => CODE_FILE_DELETE,
744	Self::FileRename { .. } => CODE_FILE_RENAME,
745	Self::FileMode { .. } => CODE_FILE_MODE,
746	Self::Mark { body: None, time: None, .. }
747	=> CODE_MARK,
748	Self::Mark { .. } => CODE_MARK_TIMED,
749	Self::Splice { .. } => CODE_SPLICE,
750	Self::Move { .. } => CODE_MOVE,
751	Self::Note { .. } => CODE_NOTE,
752	Self::Proposal { .. } => CODE_PROPOSAL,
753	Self::Said { .. } => CODE_SAID,
754	Self::Settled { .. } => CODE_SETTLED,
755	Self::Amended { .. } => CODE_AMENDED,
756	Self::Reverts { .. } => CODE_REVERTS,
757	Self::Forget { .. } => CODE_FORGET,
758	Self::Forgotten { .. } => CODE_FORGOTTEN,
759	}
760	}
761
762	/// One name for both of a mark's spellings, since the two are one operation
763	/// and a reader told otherwise would go looking for a variant that is not
764	/// there.
765	pub fn name(&self) -> &'static str {
766	match self {
767	Self::FileCreate { .. } => "FileCreate",
768	Self::FileDelete { .. } => "FileDelete",
769	Self::FileRename { .. } => "FileRename",
770	Self::FileMode { .. } => "FileMode",
771	Self::Mark { .. } => "Mark",
772	Self::Splice { .. } => "Splice",
773	Self::Move { .. } => "Move",
774	Self::Note { .. } => "Note",
775	Self::Proposal { .. } => "Proposal",
776	Self::Said { .. } => "Said",
777	Self::Settled { .. } => "Settled",
778	Self::Amended { .. } => "Amended",
779	Self::Reverts { .. } => "Reverts",
780	Self::Forget { .. } => "Forget",
781	Self::Forgotten { .. } => "Forgotten",
782	}
783	}
784
785	/// Only a lifecycle change names a file. A content operation gives `None`
786	/// because it names content and the file follows from that; a file's
787	/// creation gives `None` because the file it names is itself.
788	pub fn names_file(&self) -> Option<OpId> {
789	match self {
790	Self::FileDelete { file } => Some(*file),
791	Self::FileRename { file, .. } => Some(*file),
792	Self::FileMode { file, .. } => Some(*file),
793	_ => None,
794	}
795	}
796
797	pub fn origins(&self) -> (Option<Anchor>, Option<Anchor>) {
798	match self {
799	Self::Splice { left, right, .. } => (left, right),
800	Self::Move { left, right, .. } => (left, right),
801	Self::Forgotten { placing: Placing::Splice { left, right, .. } }
802	=> (left, right),
803	_ => (None, None),
804	}
805	}
806
807	/// The content the operation acts on, which is what decides whether two
808	/// operations were in conflict.
809	///
810	/// A note is not here, although it names content too: it asserts nothing,
811	/// neither killing content nor taking it anywhere, so a note and a
812	/// concurrent deletion of the same run are not two authors disagreeing. See
813	/// [`Op::note_on`] for the other reading.
814	pub fn regions(&self) -> &[ContentRange] {
815	match self {
816	Self::Splice { remove, .. } => remove,
817	Self::Move { src, .. } => src,
818	Self::Forgotten { placing: Placing::Splice { remove, .. } }
819	=> remove,
820	_ => &[],
821	}
822	}
823
824	pub fn note_on(&self) -> &[ContentRange] {
825	match self {
826	Self::Note { on, .. } => on,
827	_ => &[],
828	}
829	}
830
831	pub fn is_move(&self) -> bool {
832	matches!(self, Self::Move { .. })
833	}
834
835	pub fn placed_len(&self) -> u64 {
836	match self {
837	Self::Splice { insert, .. } => insert.len() as u64,
838	Self::Move { src, .. } => src.iter().map(\|r\| r.len()).sum(),
839	Self::Forgotten { placing: Placing::Splice { len, .. } }
840	=> *len,
841	_ => 0,
842	}
843	}
844
845	/// Checks the rule that replaces the file field: an operation that places
846	/// anything must carry at least one origin, that origin being what says
847	/// which file it lands in.
848	///
849	/// Enforced on the way off the wire as well as on the way into the sequence,
850	/// because an operation satisfying neither origin belongs to no file and
851	/// there is nowhere for a reader to put it.
852	pub fn check_placement(&self)
853	-> Outcome<()>
854	{
855	let (left, right) = self.origins();
856	if left.is_some() \|\| right.is_some() {
857	return Ok(());
858	}
859	match self {
860	Self::Splice { insert, .. } if !insert.is_empty() => Err(err!(
861	"A Splice inserting {} bytes carries no origin; an operation that \
862	places anything names at least one, an empty file's origin anchor \
863	being what a splice into an empty file names.", insert.len();
864	Invalid, Input, Missing)),
865	Self::Move { .. } => Err(err!(
866	"A Move carries no origin; a move always places what it names, so it \
867	always names where.";
868	Invalid, Input, Missing)),
869	Self::Forgotten { placing: Placing::Splice { len, .. } } if *len > 0 => Err(err!(
870	"A Forgotten splice of {} bytes carries no origin; the shape a forgotten \
871	insertion keeps is where it stood.", len;
872	Invalid, Input, Missing)),
873	_ => Ok(()),
874	}
875	}
876
877	/// Checks the rule that a note is about something: [`Op::Note`] must name at
878	/// least one byte, an empty list and a list of empty ranges naming none.
879	///
880	/// Such a note could never resolve to a span and would be reported forever
881	/// as a note on dead content, which is not what "dead" is for. Checked on
882	/// the way off the wire too, for the reason [`Op::check_placement`] is.
883	pub fn check_note(&self)
884	-> Outcome<()>
885	{
886	let on = match self {
887	Self::Note { on, .. } => on,
888	_ => return Ok(()),
889	};
890	if on.iter().any(\|r\| !r.is_empty()) {
891	return Ok(());
892	}
893	Err(err!(
894	"A Note is about {} content ranges, none of which names a byte; a note \
895	is about something, and a Mark is what says something about a point in \
896	history.", on.len();
897	Invalid, Input, Missing))
898	}
899
900	/// Checks the rule that a revert names what it undoes, exactly once each and
901	/// in order.
902	///
903	/// The list is held ascending and without repetition, for the reason
904	/// [`Header::from_dat`] holds the parents that way: the same set written two
905	/// ways would be two byte strings, both of which a signature would verify,
906	/// and a provenance chain cannot afford a record with two spellings. It is
907	/// refused rather than sorted, so that whoever wrote it finds out.
908	pub fn check_reverts(&self)
909	-> Outcome<()>
910	{
911	let undone = match self {
912	Self::Reverts { undone } => undone,
913	_ => return Ok(()),
914	};
915	if undone.is_empty() {
916	return Err(err!(
917	"A Reverts names no operation; a revert undoes something, and a Mark \
918	is what says something about a point in history.";
919	Invalid, Input, Missing));
920	}
921	for pair in undone.windows(2) {
922	if pair[1] <= pair[0] {
923	return Err(err!(
924	"A Reverts lists {} after {}; what a revert undoes is named \
925	ascending and without repetition.", pair[1], pair[0];
926	Decode, Input, Order));
927	}
928	}
929	Ok(())
930	}
931
932	/// Why nothing in the vocabulary undoes this operation, or `None` where
933	/// something does.
934	///
935	/// The sentence is here, and not in whoever refuses, so that a person told
936	/// no by a command and a person told no by a forge are told the same thing.
937	pub fn no_inverse(&self) -> Option<&'static str> {
938	match self {
939	Self::FileDelete { .. } => Some(
940	"a file's deletion holds its content back rather than destroying it, and \
941	no operation revives a file; a file with those bytes written again is a \
942	new file, which is what `undo` does and says"),
943	Self::Mark { .. } => Some(
944	"a mark says where somebody was at a point in the history, and the \
945	history only grows; there is nothing about it to take back"),
946	Self::Note { .. } => Some(
947	"a note is something somebody said about content, and nothing un-says \
948	it; when the content it is about goes, the note reports itself as a note \
949	on dead content"),
950	Self::Proposal { .. } => Some(
951	"a proposal is something somebody asked for, and the record of the \
952	asking grows rather than retracts; what became of it is said by writing \
953	a Settled"),
954	Self::Said { .. } => Some(
955	"a remark is something somebody said, and nothing un-says it"),
956	Self::Settled { .. } => Some(
957	"a settlement asserts what a proposal now is, and is superseded by \
958	writing another rather than undone"),
959	Self::Amended { .. } => Some(
960	"an amendment is its author saying a proposal again, and the saying \
961	grows rather than retracts; a statement got wrong is answered by \
962	writing another amendment, which is what supersedes it"),
963	Self::Reverts { .. } => Some(
964	"this names what some edits were written to undo; taking the name away \
965	would leave the edits and lose the only record of what they were for, so \
966	it is those edits that are reverted"),
967	Self::Forget { .. } => Some(
968	"a forget is the record that content was taken out of the history, and \
969	the content is gone from wherever this record has reached; nothing brings \
970	it back, and taking the record away would leave the stubs unexplained"),
971	Self::Forgotten { .. } => Some(
972	"this stands where a forgotten operation stood, and holds its shape and \
973	none of its content; there is nothing left to undo"),
974	_ => None,
975	}
976	}
977
978	/// What undoing this operation amounts to, `id` being the identity the
979	/// operation was recorded under.
980	///
981	/// The identity is asked for rather than carried because an operation does
982	/// not hold one -- the same edit written by two authors is two operations --
983	/// and an inverse needs it: what a splice inserted is named by the splice,
984	/// so undoing the insertion is a removal naming that identity and nothing
985	/// else, exact and costing no render.
986	///
987	/// A splice's two halves are not alike. The half that inserted is undone
988	/// exactly. The half that removed is not: nothing here un-buries, so what
989	/// comes back is a copy under a new identity, [`Undoing::copies`] says which
990	/// runs, and a caller must say so rather than report a clean restoration.
991	pub fn undoing(&self, id: OpId)
992	-> Outcome<Undoing>
993	{
994	if let Some(why) = self.no_inverse() {
995	return Err(err!(
996	"Nothing undoes the {} {}: {}.", self.name(), id, why;
997	Invalid, Input, Unimplemented));
998	}
999	match self {
1000	// The file did not exist before, so there is nothing to look up and the
1001	// inverse is the one operation that retires it. Note what follows: a
1002	// deletion has no inverse of its own, so this is the one undoing in the
1003	// vocabulary that cannot itself be undone.
1004	Self::FileCreate { .. } => Ok(Undoing {
1005	written: vec![Self::FileDelete { file: id }],
1006	..Undoing::default()
1007	}),
1008	Self::FileRename { file, .. } => Ok(Undoing {
1009	prior: Some(Prior::Path { file: *file }),
1010	..Undoing::default()
1011	}),
1012	Self::FileMode { file, .. } => Ok(Undoing {
1013	prior: Some(Prior::Mode { file: *file }),
1014	..Undoing::default()
1015	}),
1016	Self::Splice { remove, insert, .. } => {
1017	let mut written = Vec::new();
1018	if !insert.is_empty() {
1019	written.push(Self::Splice {
1020	left: None,
1021	right: None,
1022	remove: vec![res!(ContentRange::new(id, 0, insert.len() as u64))],
1023	insert: Arc::from(Vec::new()),
1024	});
1025	}
1026	Ok(Undoing {
1027	written,
1028	copies: remove.iter().filter(\|r\| !r.is_empty()).copied().collect(),
1029	prior: None,
1030	})
1031	},
1032	Self::Move { src, .. } => Ok(Undoing {
1033	prior: Some(Prior::Place {
1034	src: src.iter().filter(\|r\| !r.is_empty()).copied().collect(),
1035	}),
1036	..Undoing::default()
1037	}),
1038	// Everything left is refused above, and the arm is here so that a
1039	// variant added later fails loudly rather than being quietly undoable
1040	// by nothing.
1041	other => Err(err!(
1042	"The {} {} is neither undone nor refused; a new operation belongs in \
1043	one of the two.", other.name(), id;
1044	Bug, Missing)),
1045	}
1046	}
1047
1048	/// Builds the splice that puts a copy of dead content back where it was.
1049	///
1050	/// The anchor is fixed here so that two authors of a revert produce the same
1051	/// shape: the copy binds after the last byte of the run it restores. An
1052	/// anchor names content whether it is alive or dead, so this lands the copy
1053	/// exactly where the original is buried, however much of what surrounded it
1054	/// has gone since -- which no other anchor can promise, the neighbours being
1055	/// the very thing a deletion took away.
1056	///
1057	/// It is also what makes the copy readable afterwards, [`Op::restored`]
1058	/// taking the anchor and the length back apart. Nothing else in the record
1059	/// connects the two, the bytes having a new identity from the moment they
1060	/// come back.
1061	pub fn restoring(was: &ContentRange, bytes: Vec<u8>)
1062	-> Outcome<Self>
1063	{
1064	if was.is_empty() {
1065	return Err(err!(
1066	"The content {} names no byte, so there is nothing to restore.", was;
1067	Invalid, Input, Missing));
1068	}
1069	if bytes.len() as u64 != was.len() {
1070	return Err(err!(
1071	"A copy of {} bytes was offered for the content {}, which is {} bytes; a \
1072	restoration puts back what was there.", bytes.len(), was, was.len();
1073	Invalid, Input, Mismatch));
1074	}
1075	Ok(Self::Splice {
1076	left: Some(Anchor::after(ContentId::new(was.op(), was.to() - 1))),
1077	right: None,
1078	remove: Vec::new(),
1079	insert: bytes.into(),
1080	})
1081	}
1082
1083	/// The content this operation is a copy of, where it has the shape
1084	/// [`Op::restoring`] gives one: a splice that removes nothing, ends nothing,
1085	/// and binds after the last byte of the run restored.
1086	///
1087	/// This shape is not unique and is not evidence on its own. An ordinary
1088	/// insertion at the end of a file has it too. What makes a copy a copy is
1089	/// that an [`Op::Reverts`] vouches for it, and a reader that skips that
1090	/// check will credit an author for text somebody merely appended.
1091	pub fn restored(&self) -> Option<ContentRange> {
1092	let (left, right, remove, insert) = match self {
1093	Self::Splice { left, right, remove, insert } => (left, right, remove, insert),
1094	_ => return None,
1095	};
1096	if right.is_some() \|\| !remove.is_empty() \|\| insert.is_empty() {
1097	return None;
1098	}
1099	let anchor = match left {
1100	Some(a) if a.side == Side::After => a,
1101	_ => return None,
1102	};
1103	// The anchored byte is the last of the run, so the run began that many
1104	// bytes earlier. A run reaching back past the start of its own atom is not
1105	// one this ever wrote.
1106	let to = anchor.content.off + 1;
1107	let from = to.checked_sub(insert.len() as u64)?;
1108	ContentRange::new(anchor.content.op, from, to).ok()
1109	}
1110
1111	/// Checks the operation is one the sequence structure can resolve: a left
1112	/// origin binds after a byte and a right origin before one, a move may not
1113	/// name the same byte twice since a byte has one owning slot, and
1114	/// [`Op::check_placement`] must hold.
1115	pub fn validate(&self)
1116	-> Outcome<()>
1117	{
1118	let (left, right) = self.origins();
1119	if let Some(a) = left {
1120	if a.side != Side::After {
1121	return Err(err!(
1122	"An {} names {} as its left origin; a left origin binds after a \
1123	byte, not before it.", self.name(), a;
1124	Invalid, Input));
1125	}
1126	}
1127	if let Some(a) = right {
1128	if a.side != Side::Before {
1129	return Err(err!(
1130	"An {} names {} as its right origin; a right origin binds before a \
1131	byte, not after it.", self.name(), a;
1132	Invalid, Input));
1133	}
1134	}
1135	if let Self::Move { src, .. } = self {
1136	// Sorted by creating operation and then by offset, any overlap at all
1137	// shows up between neighbours.
1138	let mut spans: Vec<&ContentRange> = src.iter()
1139	.filter(\|r\| !r.is_empty())
1140	.collect();
1141	spans.sort_by_key(\|r\| (r.op(), r.from()));
1142	for pair in spans.windows(2) {
1143	if pair[0].intersects(pair[1]) {
1144	return Err(err!(
1145	"A Move names {} and {}, which overlap; one byte cannot be \
1146	moved to two places by one operation.", pair[0], pair[1];
1147	Invalid, Input, Conflict));
1148	}
1149	}
1150	}
1151	res!(self.check_placement());
1152	res!(self.check_note());
1153	res!(self.check_reverts());
1154	res!(self.check_forget());
1155	Ok(())
1156	}
1157
1158	/// Checks the rule that a forget names what it forgets, exactly once each, in
1159	/// order, and with a shape the sequence can place.
1160	///
1161	/// Ascending and without repetition for the reason [`Op::check_reverts`]
1162	/// holds its list that way: one set, one spelling, one signature. Each kept
1163	/// shape is put to the same anchor rule a live splice is, because the shape is
1164	/// what every later operation anchored inside the forgotten text resolves
1165	/// against, and a shape that could not be placed would strand all of them.
1166	pub fn check_forget(&self)
1167	-> Outcome<()>
1168	{
1169	let of = match self {
1170	Self::Forget { of, .. } => of,
1171	_ => return Ok(()),
1172	};
1173	if of.is_empty() {
1174	return Err(err!(
1175	"A Forget names no operation; a forget takes content out of the \
1176	history, and a Mark is what says something about a point in it.";
1177	Invalid, Input, Missing));
1178	}
1179	for pair in of.windows(2) {
1180	if pair[1].id <= pair[0].id {
1181	return Err(err!(
1182	"A Forget lists {} after {}; what a forget names is listed ascending \
1183	and without repetition.", pair[1].id, pair[0].id;
1184	Decode, Input, Order));
1185	}
1186	}
1187	for stub in of {
1188	res!(Self::Forgotten { placing: stub.placing.clone() }.validate());
1189	}
1190	Ok(())
1191	}
1192
1193	/// The shape this operation would keep if it were forgotten, or `None` where
1194	/// it has no content to lose.
1195	///
1196	/// This is the one place that decides what forgetting each kind of operation
1197	/// means, so that a command and a forge forget the same operation the same
1198	/// way. An operation that is all shape and no content -- a deletion, a move,
1199	/// a mode, a settlement, a revert's record, and a forget itself -- has nothing
1200	/// a forget could take, and is refused with that reason rather than recorded
1201	/// as a void that changes nothing.
1202	pub fn stub_of(&self) -> Option<Placing> {
1203	match self {
1204	Self::FileCreate { .. } => Some(Placing::File),
1205	Self::Splice { left, right, remove, insert } => Some(Placing::Splice {
1206	left: *left,
1207	right: *right,
1208	remove: remove.clone(),
1209	len: insert.len() as u64,
1210	}),
1211	Self::FileRename { .. }
1212	\| Self::Mark { .. }
1213	\| Self::Note { .. }
1214	\| Self::Proposal { .. }
1215	\| Self::Said { .. }
1216	\| Self::Amended { .. } => Some(Placing::Void),
1217	Self::FileDelete { .. }
1218	\| Self::FileMode { .. }
1219	\| Self::Move { .. }
1220	\| Self::Settled { .. }
1221	\| Self::Reverts { .. }
1222	\| Self::Forget { .. }
1223	\| Self::Forgotten { .. } => None,
1224	}
1225	}
1226
1227	/// The shape is `[code, field, ...]`, the fields in declaration order.
1228	///
1229	/// Byte payloads use [`Dat::BU64`] rather than [`Dat::BU8`], whose length
1230	/// field is a single byte and so keeps only the low eight bits of the
1231	/// length of anything longer than 255 bytes. A path is a byte payload for the
1232	/// same reason a path is not a string: neither is the caller's to constrain.
1233	pub fn to_dat(&self) -> Dat {
1234	match self {
1235	Self::FileCreate { path } => Dat::List(vec![
1236	Dat::U8(CODE_FILE_CREATE),
1237	Dat::BU64(path.clone()),
1238	]),
1239	Self::FileDelete { file } => Dat::List(vec![
1240	Dat::U8(CODE_FILE_DELETE),
1241	file.to_dat(),
1242	]),
1243	Self::FileRename { file, path } => Dat::List(vec![
1244	Dat::U8(CODE_FILE_RENAME),
1245	file.to_dat(),
1246	Dat::BU64(path.clone()),
1247	]),
1248	Self::FileMode { file, mode } => Dat::List(vec![
1249	Dat::U8(CODE_FILE_MODE),
1250	file.to_dat(),
1251	mode.to_dat(),
1252	]),
1253	// Two spellings of one variant, chosen by what the mark carries: the
1254	// short one is what every mark written before the fields existed
1255	// says, byte for byte, and the long one is what a mark carrying
1256	// either of them says. Which is written is not the author's choice,
1257	// so the encoding stays canonical and a mark has one signature.
1258	Self::Mark { name, body: None, time: None } => Dat::List(vec![
1259	Dat::U8(CODE_MARK),
1260	Dat::Str(name.clone()),
1261	]),
1262	Self::Mark { name, body, time } => Dat::List(vec![
1263	Dat::U8(CODE_MARK_TIMED),
1264	Dat::Str(name.clone()),
1265	opt_bytes_to_dat(body),
1266	opt_u64_to_dat(time),
1267	]),
1268	Self::Splice { left, right, remove, insert } => Dat::List(vec![
1269	Dat::U8(CODE_SPLICE),
1270	Anchor::opt_to_dat(left),
1271	Anchor::opt_to_dat(right),
1272	Dat::List(remove.iter().map(\|r\| r.to_dat()).collect()),
1273	Dat::BU64(insert.to_vec()),
1274	]),
1275	Self::Move { src, left, right } => Dat::List(vec![
1276	Dat::U8(CODE_MOVE),
1277	Dat::List(src.iter().map(\|r\| r.to_dat()).collect()),
1278	Anchor::opt_to_dat(left),
1279	Anchor::opt_to_dat(right),
1280	]),
1281	Self::Note { on, text } => Dat::List(vec![
1282	Dat::U8(CODE_NOTE),
1283	Dat::List(on.iter().map(\|r\| r.to_dat()).collect()),
1284	Dat::BU64(text.clone()),
1285	]),
1286	Self::Proposal { title, body, voice, time } => Dat::List(vec![
1287	Dat::U8(CODE_PROPOSAL),
1288	Dat::Str(title.clone()),
1289	Dat::BU64(body.clone()),
1290	Dat::Str(voice.clone()),
1291	Dat::U64(*time),
1292	]),
1293	Self::Said { on, text, voice, time } => Dat::List(vec![
1294	Dat::U8(CODE_SAID),
1295	on.to_dat(),
1296	Dat::BU64(text.clone()),
1297	Dat::Str(voice.clone()),
1298	Dat::U64(*time),
1299	]),
1300	Self::Settled { on, state, mark, time } => Dat::List(vec![
1301	Dat::U8(CODE_SETTLED),
1302	on.to_dat(),
1303	state.to_dat(),
1304	opt_id_to_dat(mark),
1305	Dat::U64(*time),
1306	]),
1307	Self::Amended { on, title, body, voice, time } => Dat::List(vec![
1308	Dat::U8(CODE_AMENDED),
1309	on.to_dat(),
1310	Dat::Str(title.clone()),
1311	Dat::BU64(body.clone()),
1312	Dat::Str(voice.clone()),
1313	Dat::U64(*time),
1314	]),
1315	Self::Reverts { undone } => Dat::List(vec![
1316	Dat::U8(CODE_REVERTS),
1317	Dat::List(undone.iter().map(\|u\| u.to_dat()).collect()),
1318	]),
1319	Self::Forget { of, reason, time } => Dat::List(vec![
1320	Dat::U8(CODE_FORGET),
1321	Dat::List(of.iter().map(\|s\| s.to_dat()).collect()),
1322	Dat::BU64(reason.clone()),
1323	Dat::U64(*time),
1324	]),
1325	Self::Forgotten { placing } => Dat::List(vec![
1326	Dat::U8(CODE_FORGOTTEN),
1327	placing.to_dat(),
1328	]),
1329	}
1330	}
1331
1332	/// The placement rule is checked here rather than left to the sequence,
1333	/// because an operation that places bytes and names no origin belongs to no
1334	/// file and no later stage could decide one for it. [`Op::check_note`] is
1335	/// checked here for the same reason: a note about nothing resolves to nothing,
1336	/// wherever it is read. So is [`Op::check_reverts`], since a list that arrives
1337	/// out of order is a second byte spelling of a set that has one.
1338	pub fn from_dat(dat: &Dat)
1339	-> Outcome<Self>
1340	{
1341	let v = match dat {
1342	Dat::List(v) if !v.is_empty() => v,
1343	_ => return Err(err!(
1344	"An Op expects a non-empty Dat::List, got {:?}.", dat;
1345	Decode, Input, Mismatch)),
1346	};
1347	let code = match &v[0] {
1348	Dat::U8(c) => *c,
1349	other => return Err(err!(
1350	"An Op code expects Dat::U8, got {:?}.", other;
1351	Decode, Input, Mismatch)),
1352	};
1353	let op = match code {
1354	CODE_FILE_CREATE => {
1355	res!(expect_len(v, 2, "FileCreate"));
1356	Self::FileCreate {
1357	path: res!(as_bytes(&v[1], "FileCreate path")),
1358	}
1359	},
1360	CODE_FILE_DELETE => {
1361	res!(expect_len(v, 2, "FileDelete"));
1362	Self::FileDelete {
1363	file: res!(OpId::from_dat(&v[1])),
1364	}
1365	},
1366	CODE_FILE_RENAME => {
1367	res!(expect_len(v, 3, "FileRename"));
1368	Self::FileRename {
1369	file: res!(OpId::from_dat(&v[1])),
1370	path: res!(as_bytes(&v[2], "FileRename path")),
1371	}
1372	},
1373	CODE_FILE_MODE => {
1374	res!(expect_len(v, 3, "FileMode"));
1375	Self::FileMode {
1376	file: res!(OpId::from_dat(&v[1])),
1377	mode: res!(Mode::from_dat(&v[2])),
1378	}
1379	},
1380	// Both spellings decode to the one variant, so nothing downstream has
1381	// to know which of them it was read from.
1382	CODE_MARK => {
1383	res!(expect_len(v, 2, "Mark"));
1384	Self::Mark {
1385	name: res!(as_str(&v[1], "Mark name")),
1386	body: None,
1387	time: None,
1388	}
1389	},
1390	CODE_MARK_TIMED => {
1391	res!(expect_len(v, 4, "Mark"));
1392	let body = res!(as_opt_bytes(&v[2], "Mark body"));
1393	let time = res!(as_opt_u64(&v[3], "Mark time"));
1394	// The long spelling is refused where it says nothing the short one
1395	// could not, rather than being quietly read as the short one.
1396	// Otherwise a mark would have two encodings, both verifying against
1397	// a signature, which is the thing [`Header::from_dat`] refuses for
1398	// the same reason.
1399	if body.is_none() && time.is_none() {
1400	return Err(err!(
1401	"A Mark named {:?} is written at wire code {} carrying neither a \
1402	body nor a time; a mark with neither is written at code {}, and \
1403	an operation has one encoding.",
1404	res!(as_str(&v[1], "Mark name")), CODE_MARK_TIMED, CODE_MARK;
1405	Decode, Input, Invalid));
1406	}
1407	Self::Mark {
1408	name: res!(as_str(&v[1], "Mark name")),
1409	body,
1410	time,
1411	}
1412	},
1413	CODE_SPLICE => {
1414	res!(expect_len(v, 5, "Splice"));
1415	Self::Splice {
1416	left: res!(Anchor::opt_from_dat(&v[1])),
1417	right: res!(Anchor::opt_from_dat(&v[2])),
1418	remove: res!(as_ranges(&v[3], "Splice remove")),
1419	insert: res!(as_bytes(&v[4], "Splice insert")).into(),
1420	}
1421	},
1422	CODE_MOVE => {
1423	res!(expect_len(v, 4, "Move"));
1424	Self::Move {
1425	src: res!(as_ranges(&v[1], "Move src")),
1426	left: res!(Anchor::opt_from_dat(&v[2])),
1427	right: res!(Anchor::opt_from_dat(&v[3])),
1428	}
1429	},
1430	CODE_NOTE => {
1431	res!(expect_len(v, 3, "Note"));
1432	Self::Note {
1433	on: res!(as_ranges(&v[1], "Note on")),
1434	text: res!(as_bytes(&v[2], "Note text")),
1435	}
1436	},
1437	CODE_PROPOSAL => {
1438	res!(expect_len(v, 5, "Proposal"));
1439	Self::Proposal {
1440	title: res!(as_str(&v[1], "Proposal title")),
1441	body: res!(as_bytes(&v[2], "Proposal body")),
1442	voice: res!(as_str(&v[3], "Proposal voice")),
1443	time: res!(as_u64(&v[4], "Proposal time")),
1444	}
1445	},
1446	CODE_SAID => {
1447	res!(expect_len(v, 5, "Said"));
1448	Self::Said {
1449	on: res!(OpId::from_dat(&v[1])),
1450	text: res!(as_bytes(&v[2], "Said text")),
1451	voice: res!(as_str(&v[3], "Said voice")),
1452	time: res!(as_u64(&v[4], "Said time")),
1453	}
1454	},
1455	CODE_SETTLED => {
1456	res!(expect_len(v, 5, "Settled"));
1457	Self::Settled {
1458	on: res!(OpId::from_dat(&v[1])),
1459	state: res!(Settled::from_dat(&v[2])),
1460	mark: res!(as_opt_id(&v[3], "Settled mark")),
1461	time: res!(as_u64(&v[4], "Settled time")),
1462	}
1463	},
1464	CODE_AMENDED => {
1465	res!(expect_len(v, 6, "Amended"));
1466	Self::Amended {
1467	on: res!(OpId::from_dat(&v[1])),
1468	title: res!(as_str(&v[2], "Amended title")),
1469	body: res!(as_bytes(&v[3], "Amended body")),
1470	voice: res!(as_str(&v[4], "Amended voice")),
1471	time: res!(as_u64(&v[5], "Amended time")),
1472	}
1473	},
1474	CODE_REVERTS => {
1475	res!(expect_len(v, 2, "Reverts"));
1476	Self::Reverts {
1477	undone: res!(as_ids(&v[1], "Reverts undone")),
1478	}
1479	},
1480	CODE_FORGET => {
1481	res!(expect_len(v, 4, "Forget"));
1482	let of = match &v[1] {
1483	Dat::List(items) => {
1484	let mut out = Vec::with_capacity(items.len());
1485	for item in items {
1486	out.push(res!(Stub::from_dat(item)));
1487	}
1488	out
1489	},
1490	other => return Err(err!(
1491	"Forget of is a list of stubs, not {:?}.", other;
1492	Decode, Input, Invalid)),
1493	};
1494	Self::Forget {
1495	of,
1496	reason: res!(as_bytes(&v[2], "Forget reason")),
1497	time: res!(as_u64(&v[3], "Forget time")),
1498	}
1499	},
1500	CODE_FORGOTTEN => {
1501	res!(expect_len(v, 2, "Forgotten"));
1502	Self::Forgotten {
1503	placing: res!(Placing::from_dat(&v[1])),
1504	}
1505	},
1506	other => return Err(err!(
1507	"Op code {} is not recognised.", other;
1508	Decode, Input, Invalid)),
1509	};
1510	res!(op.check_placement());
1511	res!(op.check_note());
1512	res!(op.check_reverts());
1513	res!(op.check_forget());
1514	Ok(op)
1515	}
1516
1517	/// A varint length followed by the binary daticle form. The prefix lets a
1518	/// consumer skip an operation it does not need to read, and lets several be
1519	/// laid end to end in one buffer.
1520	pub fn encode_into(&self, buf: &mut Vec<u8>)
1521	-> Outcome<()>
1522	{
1523	let body = res!(self.to_dat().to_bytes(Vec::new()));
1524	varint_encode(body.len() as u64, buf);
1525	buf.extend_from_slice(&body);
1526	Ok(())
1527	}
1528
1529	pub fn encode(&self)
1530	-> Outcome<Vec<u8>>
1531	{
1532	let mut buf = Vec::new();
1533	res!(self.encode_into(&mut buf));
1534	Ok(buf)
1535	}
1536
1537	pub fn decode(buf: &[u8])
1538	-> Outcome<(Self, usize)>
1539	{
1540	let (dat, end) = res!(decode_framed(buf, "Op"));
1541	Ok((res!(Self::from_dat(&dat)), end))
1542	}
1543
1544	/// Hashes the canonical encoding. The choice of hash function is deliberately
1545	/// not made here: which one is right depends on what else has to compute the
1546	/// same value -- a browser limited to what its platform offers, a peer group
1547	/// that has already agreed on one -- so the caller brings it.
1548	pub fn hash<H: Hasher, const S: usize>(&self, hasher: H, salt: [u8; S])
1549	-> Outcome<Hash<S>>
1550	{
1551	let bytes = res!(self.encode());
1552	Ok(hasher.hash(&[&bytes], salt))
1553	}
1554
1555	pub fn decode_all(buf: &[u8])
1556	-> Outcome<Self>
1557	{
1558	let (op, len) = res!(Self::decode(buf));
1559	if len != buf.len() {
1560	return Err(err!(
1561	"An Op consumed {} of {} bytes, leaving {} trailing.",
1562	len, buf.len(), buf.len() - len;
1563	Decode, Input, Excessive));
1564	}
1565	Ok(op)
1566	}
1567	}
1568
1569
1570	/// What every operation carries whatever it says: its own name, and the names
1571	/// of the operations its author had already seen.
1572	///
1573	/// The parents are the author's frontier at the moment of writing, which is
1574	/// what turns a heap of operations into a partial order. Two operations are
1575	/// concurrent exactly when neither is reachable from the other by following
1576	/// parents, and that question -- not the accident of which arrived first -- is
1577	/// what decides whether two edits to the same bytes were a conflict or a
1578	/// sequence.
1579	///
1580	/// Both fields are private, because the canonical form is an invariant and not a
1581	/// convention: parents are held sorted and without repetition, and an operation
1582	/// is never its own parent. Two byte spellings of one frontier would both verify
1583	/// against a signature, which is not a property a provenance chain can afford.
1584	#[derive(Clone, Debug, Default, Eq, PartialEq)]
1585	pub struct Header {
1586	id: OpId,
1587	parents: Vec<OpId>, // ascending, without repetition
1588	}
1589
1590	impl Header {
1591	/// Sorts the parents and drops repetitions, which is where the canonical
1592	/// form is established.
1593	pub fn new(id: OpId, parents: Vec<OpId>)
1594	-> Outcome<Self>
1595	{
1596	let mut parents = parents;
1597	parents.sort();
1598	parents.dedup();
1599	if parents.binary_search(&id).is_ok() {
1600	return Err(err!(
1601	"The operation {} names itself as one of its own parents.", id;
1602	Invalid, Input, Conflict));
1603	}
1604	Ok(Self { id, parents })
1605	}
1606
1607	/// A root operation is one written against nothing.
1608	pub fn root(id: OpId) -> Self {
1609	Self { id, parents: Vec::new() }
1610	}
1611
1612	pub const fn id(&self) -> OpId {
1613	self.id
1614	}
1615
1616	/// The author's frontier when the operation was written, ascending and
1617	/// without repetition.
1618	pub fn parents(&self) -> &[OpId] {
1619	&self.parents
1620	}
1621
1622	pub fn is_root(&self) -> bool {
1623	self.parents.is_empty()
1624	}
1625
1626	/// The shape is `[id, [parent, ...]]`.
1627	pub fn to_dat(&self) -> Dat {
1628	Dat::List(vec![
1629	self.id.to_dat(),
1630	Dat::List(self.parents.iter().map(\|p\| p.to_dat()).collect()),
1631	])
1632	}
1633
1634	/// Parents out of order, repeated, or naming the operation itself are
1635	/// refused rather than normalised, so that the encoding stays canonical.
1636	pub fn from_dat(dat: &Dat)
1637	-> Outcome<Self>
1638	{
1639	let v = match dat {
1640	Dat::List(v) if v.len() == 2 => v,
1641	_ => return Err(err!(
1642	"A Header expects a 2-element Dat::List, got {:?}.", dat;
1643	Decode, Input, Mismatch)),
1644	};
1645	let id = res!(OpId::from_dat(&v[0]));
1646	let listed = match &v[1] {
1647	Dat::List(p) => p,
1648	other => return Err(err!(
1649	"A Header's parents expect Dat::List, got {:?}.", other;
1650	Decode, Input, Mismatch)),
1651	};
1652	let mut parents = Vec::with_capacity(listed.len());
1653	for item in listed {
1654	let p = res!(OpId::from_dat(item));
1655	if let Some(last) = parents.last() {
1656	if p <= *last {
1657	return Err(err!(
1658	"A Header of {} lists the parent {} after {}; parents are \
1659	encoded ascending and without repetition.", id, p, last;
1660	Decode, Input, Order));
1661	}
1662	}
1663	if p == id {
1664	return Err(err!(
1665	"A Header of {} names itself as one of its own parents.", id;
1666	Decode, Input, Conflict));
1667	}
1668	parents.push(p);
1669	}
1670	Ok(Self { id, parents })
1671	}
1672	}
1673
1674
1675	/// One whole operation as history records it: the header that names it and
1676	/// places it in the graph, and the operation itself.
1677	///
1678	/// This is the unit that is logged, sealed into an [`crate::envelope::Envelope`]
1679	/// and written into a segment. The header is not part of the operation because
1680	/// the same edit written by two authors is two operations, and the vocabulary
1681	/// should not have to say so six times over.
1682	#[derive(Clone, Debug, Eq, PartialEq)]
1683	pub struct Record {
1684	pub head: Header,
1685	pub op: Op,
1686	}
1687
1688	impl Record {
1689	pub fn new(head: Header, op: Op) -> Self {
1690	Self { head, op }
1691	}
1692
1693	pub fn root(id: OpId, op: Op) -> Self {
1694	Self { head: Header::root(id), op }
1695	}
1696
1697	pub fn id(&self) -> OpId {
1698	self.head.id()
1699	}
1700
1701	pub fn parents(&self) -> &[OpId] {
1702	self.head.parents()
1703	}
1704
1705	/// The shape is `[head, op]`.
1706	pub fn to_dat(&self) -> Dat {
1707	Dat::List(vec![
1708	self.head.to_dat(),
1709	self.op.to_dat(),
1710	])
1711	}
1712
1713	pub fn from_dat(dat: &Dat)
1714	-> Outcome<Self>
1715	{
1716	let v = match dat {
1717	Dat::List(v) if v.len() == 2 => v,
1718	_ => return Err(err!(
1719	"A Record expects a 2-element Dat::List, got {:?}.", dat;
1720	Decode, Input, Mismatch)),
1721	};
1722	Ok(Self {
1723	head: res!(Header::from_dat(&v[0])),
1724	op: res!(Op::from_dat(&v[1])),
1725	})
1726	}
1727
1728	pub fn encode_into(&self, buf: &mut Vec<u8>)
1729	-> Outcome<()>
1730	{
1731	let body = res!(self.to_dat().to_bytes(Vec::new()));
1732	varint_encode(body.len() as u64, buf);
1733	buf.extend_from_slice(&body);
1734	Ok(())
1735	}
1736
1737	pub fn encode(&self)
1738	-> Outcome<Vec<u8>>
1739	{
1740	let mut buf = Vec::new();
1741	res!(self.encode_into(&mut buf));
1742	Ok(buf)
1743	}
1744
1745	pub fn decode(buf: &[u8])
1746	-> Outcome<(Self, usize)>
1747	{
1748	let (dat, end) = res!(decode_framed(buf, "Record"));
1749	Ok((res!(Self::from_dat(&dat)), end))
1750	}
1751
1752	pub fn decode_all(buf: &[u8])
1753	-> Outcome<Self>
1754	{
1755	let (rec, len) = res!(Self::decode(buf));
1756	if len != buf.len() {
1757	return Err(err!(
1758	"A Record consumed {} of {} bytes, leaving {} trailing.",
1759	len, buf.len(), buf.len() - len;
1760	Decode, Input, Excessive));
1761	}
1762	Ok(rec)
1763	}
1764
1765	/// Covers the parents along with the operation.
1766	///
1767	/// This value is not the digest a segment stores for the record: a segment
1768	/// digests the record's kind byte and unframed body, while this hashes the
1769	/// framed encoding, so the two are computed over different byte strings
1770	/// and will not match.
1771	pub fn hash<H: Hasher, const S: usize>(&self, hasher: H, salt: [u8; S])
1772	-> Outcome<Hash<S>>
1773	{
1774	let bytes = res!(self.encode());
1775	Ok(hasher.hash(&[&bytes], salt))
1776	}
1777	}
1778
1779
1780	fn decode_framed(buf: &[u8], what: &str)
1781	-> Outcome<(Dat, usize)>
1782	{
1783	let (len, hdr) = res!(varint_decode(buf));
1784	let len = len as usize;
1785	let end = match hdr.checked_add(len) {
1786	Some(e) => e,
1787	None => return Err(err!(
1788	"A {} declares a length of {} bytes, which overflows the buffer \
1789	offset.", what, len;
1790	Decode, Input, Overflow)),
1791	};
1792	if end > buf.len() {
1793	return Err(err!(
1794	"A {} declares {} bytes of body but only {} remain.",
1795	what, len, buf.len() - hdr;
1796	Decode, Input, Missing));
1797	}
1798	let (dat, used) = res!(Dat::from_bytes(&buf[hdr..end]));
1799	if used != len {
1800	return Err(err!(
1801	"A {} body of {} bytes decoded from only {} of them.", what, len, used;
1802	Decode, Input, Mismatch));
1803	}
1804	Ok((dat, end))
1805	}
1806
1807	/// Refuses an operation whose list is not EXACTLY `want` elements long.
1808	///
1809	/// This exact-length check is why the operation wire format is strictly
1810	/// versioned and forward-INcompatible, which is not obvious from the code and
1811	/// is worth knowing before touching an op: adding a field to an existing op (a
1812	/// new trailing list element in its `to_dat`), or adding a new op code, makes
1813	/// every reader running an older build reject it HERE -- "expects N ... got
1814	/// N+1". So an op-format change is never a local edit; it is a hard, fleet-wide
1815	/// readers-first rollout -- every replica must run a build that accepts the new
1816	/// shape BEFORE any replica writes it -- and since fe2o3 and the forge repos are
1817	/// now publicly cloneable, it reaches external cloners on old clients that
1818	/// cannot be upgraded. Carry new information in an EXISTING op (a `Said` comment,
1819	/// say) in preference to extending one; a new wire code is no cheaper here.
1820	fn expect_len(v: &[Dat], want: usize, what: &str)
1821	-> Outcome<()>
1822	{
1823	if v.len() != want {
1824	return Err(err!(
1825	"An Op::{} expects {} list elements, got {}.", what, want, v.len();
1826	Decode, Input, Mismatch));
1827	}
1828	Ok(())
1829	}
1830
1831	fn as_str(dat: &Dat, what: &str)
1832	-> Outcome<String>
1833	{
1834	match dat {
1835	Dat::Str(s) => Ok(s.clone()),
1836	other => Err(err!(
1837	"An Op {} expects Dat::Str, got {:?}.", what, other;
1838	Decode, Input, Mismatch)),
1839	}
1840	}
1841
1842	fn as_ranges(dat: &Dat, what: &str)
1843	-> Outcome<Vec<ContentRange>>
1844	{
1845	match dat {
1846	Dat::List(v) => {
1847	let mut out = Vec::with_capacity(v.len());
1848	for item in v {
1849	out.push(res!(ContentRange::from_dat(item)));
1850	}
1851	Ok(out)
1852	},
1853	other => Err(err!(
1854	"An Op {} expects Dat::List, got {:?}.", what, other;
1855	Decode, Input, Mismatch)),
1856	}
1857	}
1858
1859	fn as_bytes(dat: &Dat, what: &str)
1860	-> Outcome<Vec<u8>>
1861	{
1862	match dat {
1863	Dat::BU64(b) => Ok(b.clone()),
1864	other => Err(err!(
1865	"An Op {} expects Dat::BU64, got {:?}.", what, other;
1866	Decode, Input, Mismatch)),
1867	}
1868	}
1869
1870	fn as_ids(dat: &Dat, what: &str)
1871	-> Outcome<Vec<OpId>>
1872	{
1873	match dat {
1874	Dat::List(v) => {
1875	let mut out = Vec::with_capacity(v.len());
1876	for item in v {
1877	out.push(res!(OpId::from_dat(item)));
1878	}
1879	Ok(out)
1880	},
1881	other => Err(err!(
1882	"An Op {} expects Dat::List, got {:?}.", what, other;
1883	Decode, Input, Mismatch)),
1884	}
1885	}
1886
1887	/// A time is exactly this and nothing narrower: seconds since the Unix epoch, in
1888	/// UTC, read by whoever wrote the operation and never recomputed afterwards,
1889	/// since a second reading would be a different operation under the same
1890	/// signature.
1891	fn as_u64(dat: &Dat, what: &str)
1892	-> Outcome<u64>
1893	{
1894	match dat {
1895	Dat::U64(n) => Ok(*n),
1896	other => Err(err!(
1897	"An Op {} expects Dat::U64, got {:?}.", what, other;
1898	Decode, Input, Mismatch)),
1899	}
1900	}
1901
1902	fn opt_bytes_to_dat(body: &Option<Vec<u8>>) -> Dat {
1903	Dat::Opt(Box::new(body.as_ref().map(\|b\| Dat::BU64(b.clone()))))
1904	}
1905
1906	fn as_opt_bytes(dat: &Dat, what: &str)
1907	-> Outcome<Option<Vec<u8>>>
1908	{
1909	match dat {
1910	Dat::Opt(boxed) => match boxed.as_ref() {
1911	Some(inner) => Ok(Some(res!(as_bytes(inner, what)))),
1912	None => Ok(None),
1913	},
1914	other => Err(err!(
1915	"An optional Op {} expects Dat::Opt, got {:?}.", what, other;
1916	Decode, Input, Mismatch)),
1917	}
1918	}
1919
1920	fn opt_u64_to_dat(time: &Option<u64>) -> Dat {
1921	Dat::Opt(Box::new(time.map(Dat::U64)))
1922	}
1923
1924	fn as_opt_u64(dat: &Dat, what: &str)
1925	-> Outcome<Option<u64>>
1926	{
1927	match dat {
1928	Dat::Opt(boxed) => match boxed.as_ref() {
1929	Some(inner) => Ok(Some(res!(as_u64(inner, what)))),
1930	None => Ok(None),
1931	},
1932	other => Err(err!(
1933	"An optional Op {} expects Dat::Opt, got {:?}.", what, other;
1934	Decode, Input, Mismatch)),
1935	}
1936	}
1937
1938	fn opt_id_to_dat(id: &Option<OpId>) -> Dat {
1939	Dat::Opt(Box::new(id.as_ref().map(\|i\| i.to_dat())))
1940	}
1941
1942	fn as_opt_id(dat: &Dat, what: &str)
1943	-> Outcome<Option<OpId>>
1944	{
1945	match dat {
1946	Dat::Opt(boxed) => match boxed.as_ref() {
1947	Some(inner) => Ok(Some(res!(OpId::from_dat(inner)))),
1948	None => Ok(None),
1949	},
1950	other => Err(err!(
1951	"An optional Op {} expects Dat::Opt, got {:?}.", what, other;
1952	Decode, Input, Mismatch)),
1953	}
1954	}
1955
1956
1957	// Reachable from the other modules' tests because `samples` is the crate's one
1958	// list of every operation variant, and a second list would be the one that goes
1959	// stale when the vocabulary grows.
1960	#[cfg(test)]
1961	pub(crate) mod tests {
1962	use super::*;
1963
1964	use crate::id::{
1965	ContentId,
1966	ReplicaId,
1967	};
1968
1969	/// A content range of the given replica's first operation. The bounds are put
1970	/// in order before the constructor sees them, so the helper is total and can
1971	/// be called from fixtures that return an operation rather than an
1972	/// [`Outcome`].
1973	fn range(replica: u64, from: u64, to: u64) -> ContentRange {
1974	let op = OpId::new(ReplicaId::new(replica), 1);
1975	ContentRange::new(op, from.min(to), from.max(to)).unwrap_or_default()
1976	}
1977
1978	fn content(replica: u64, off: u64) -> ContentId {
1979	ContentId::new(OpId::new(ReplicaId::new(replica), 1), off)
1980	}
1981
1982	fn oid(replica: u64, counter: u64) -> OpId {
1983	OpId::new(ReplicaId::new(replica), counter)
1984	}
1985
1986	/// One of every variant, including payloads that stress the encoding.
1987	pub(crate) fn samples() -> Vec<Op> {
1988	vec![
1989	Op::FileCreate { path: b"src/lib.rs".to_vec() },
1990	Op::FileDelete { file: oid(1, 1) },
1991	Op::FileRename {
1992	file: oid(2, 5),
1993	path: b"c/d.txt".to_vec(),
1994	},
1995	// Every mode the vocabulary spells, including the one a file has
1996	// anyway, which an author may still want said out loud.
1997	Op::FileMode { file: oid(2, 5), mode: Mode::Normal },
1998	Op::FileMode { file: oid(2, 5), mode: Mode::Executable },
1999	Op::FileMode { file: oid(7, 1), mode: Mode::Symlink },
2000	// An insertion into an empty file, anchored after its origin anchor,
2001	// which is what an empty file has instead of nothing.
2002	Op::Splice {
2003	left: Some(Anchor::origin(oid(1, 1))),
2004	right: None,
2005	remove: Vec::new(),
2006	insert: b"hello".to_vec().into(),
2007	},
2008	// A deletion, which places nothing and so needs no origin.
2009	Op::Splice {
2010	left: None,
2011	right: None,
2012	remove: vec![range(1, 12, 17)],
2013	insert: Vec::new().into(),
2014	},
2015	// A replacement whose payload exceeds what a BU8 length can hold,
2016	// killing several fragmented runs at once.
2017	Op::Splice {
2018	left: Some(Anchor::after(content(2, u64::MAX))),
2019	right: Some(Anchor::before(content(3, 0))),
2020	remove: vec![
2021	range(1, 0, u64::MAX),
2022	range(4, 7, 9),
2023	],
2024	insert: vec![0xa5; 1000].into(),
2025	},
2026	// An empty path, and a path that is not UTF-8 at all, which the old
2027	// vocabulary could not spell.
2028	Op::FileCreate { path: Vec::new() },
2029	Op::FileCreate { path: vec![0xff, 0xfe, 0x2f, 0x00, 0x80] },
2030	Op::Mark { name: fmt!("release-caf\u{e9}"), body: None, time: None },
2031	// Every combination the mark's two spellings cover: the short one,
2032	// then a body alone, a time alone, and both. A body longer than a
2033	// single byte length field could hold, and one that is not UTF-8,
2034	// since a mark's body is no more this crate's to decode than a note's
2035	// text is.
2036	Op::Mark {
2037	name: fmt!("v2"),
2038	body: Some(b"what this release is for".to_vec()),
2039	time: None,
2040	},
2041	Op::Mark {
2042	name: fmt!("v3"),
2043	body: None,
2044	time: Some(1_755_400_329),
2045	},
2046	Op::Mark {
2047	name: fmt!("v4"),
2048	body: Some(vec![0xc3; 900]),
2049	time: Some(u64::MAX),
2050	},
2051	Op::Mark {
2052	name: String::new(),
2053	body: Some(Vec::new()),
2054	time: Some(0),
2055	},
2056	// A proposal, its discussion and its outcome.
2057	Op::Proposal {
2058	title: fmt!("Carry a body on a mark"),
2059	body: b"A mark names a point and says nothing about it.".to_vec(),
2060	voice: fmt!("wren"),
2061	time: 1_755_400_000,
2062	},
2063	Op::Proposal {
2064	title: String::new(),
2065	body: vec![0xff; 700],
2066	voice: String::new(),
2067	time: 0,
2068	},
2069	Op::Said {
2070	on: oid(3, 4),
2071	text: b"Agreed, provided the old bytes do not move.".to_vec(),
2072	voice: fmt!("caf\u{e9}"),
2073	time: 1_755_400_100,
2074	},
2075	Op::Said {
2076	on: oid(u64::MAX, u64::MAX),
2077	text: Vec::new(),
2078	voice: String::new(),
2079	time: u64::MAX,
2080	},
2081	// Every state, and both spellings of the mark that closed it.
2082	Op::Settled {
2083	on: oid(3, 4),
2084	state: Settled::Open,
2085	mark: None,
2086	time: 1_755_400_200,
2087	},
2088	Op::Settled {
2089	on: oid(3, 4),
2090	state: Settled::Accepted,
2091	mark: Some(oid(9, 2)),
2092	time: 1_755_400_201,
2093	},
2094	Op::Settled {
2095	on: oid(3, 4),
2096	state: Settled::Declined,
2097	mark: None,
2098	time: 1_755_400_202,
2099	},
2100	Op::Settled {
2101	on: oid(3, 4),
2102	state: Settled::Done,
2103	mark: Some(oid(1, u64::MAX)),
2104	time: u64::MAX,
2105	},
2106	// An amendment by the voice that opened the proposal, one whose body
2107	// exceeds a single byte length field, and the empty extreme -- the same
2108	// three shapes the proposal above is sampled at, since an amendment
2109	// carries what a proposal carries and must encode the same way.
2110	Op::Amended {
2111	on: oid(3, 4),
2112	title: fmt!("Carry a body on a mark, and say when"),
2113	body: b"A mark names a point and says nothing about it or when.".to_vec(),
2114	voice: fmt!("wren"),
2115	time: 1_755_400_300,
2116	},
2117	Op::Amended {
2118	on: oid(3, 4),
2119	title: fmt!("caf\u{e9}"),
2120	body: vec![0xff; 700],
2121	voice: fmt!("caf\u{e9}"),
2122	time: 1_755_400_301,
2123	},
2124	Op::Amended {
2125	on: oid(u64::MAX, u64::MAX),
2126	title: String::new(),
2127	body: Vec::new(),
2128	voice: String::new(),
2129	time: u64::MAX,
2130	},
2131	// A revert of one operation, of several by one author, and of several
2132	// spread across authors and out to the ends of the identifier space.
2133	Op::Reverts { undone: vec![oid(2, 7)] },
2134	Op::Reverts { undone: vec![oid(1, 1), oid(1, 2), oid(3, 1)] },
2135	Op::Reverts { undone: vec![
2136	oid(0, 1),
2137	oid(4, u64::MAX),
2138	oid(u64::MAX, 1),
2139	] },
2140	// A move of one run into the middle of a file.
2141	Op::Move {
2142	src: vec![range(1, 0, 40)],
2143	left: Some(Anchor::after(content(2, 3))),
2144	right: Some(Anchor::before(content(2, 4))),
2145	},
2146	// A move to the very start of a file, of a run fragmented by the
2147	// edits it has already survived: the destination is the gap after
2148	// that file's origin anchor.
2149	Op::Move {
2150	src: vec![
2151	range(1, 0, 4),
2152	range(3, 7, 9),
2153	range(1, 4, 40),
2154	],
2155	left: Some(Anchor::origin(oid(9, 1))),
2156	right: Some(Anchor::before(content(1, 41))),
2157	},
2158	// A move to the end of a file, whose destination is bounded by
2159	// nothing on the right.
2160	Op::Move {
2161	src: vec![range(u64::MAX, 0, u64::MAX)],
2162	left: Some(Anchor::after(content(7, u64::MAX))),
2163	right: None,
2164	},
2165	// A move of nothing to somewhere in particular: the degenerate shape
2166	// the codec still has to spell.
2167	Op::Move {
2168	src: Vec::new(),
2169	left: None,
2170	right: Some(Anchor::before(content(1, 0))),
2171	},
2172	// A note on one run.
2173	Op::Note {
2174	on: vec![range(1, 4, 19)],
2175	text: b"this loop is quadratic".to_vec(),
2176	},
2177	// A note on content already fragmented across two atoms, whose text is
2178	// longer than a single byte length field could hold and is not UTF-8.
2179	Op::Note {
2180	on: vec![
2181	range(2, 0, u64::MAX),
2182	range(5, 7, 9),
2183	],
2184	text: vec![0xc3; 900],
2185	},
2186	// A note whose list carries an empty range beside a real one, which is
2187	// legal: what is refused is a note that names no byte at all.
2188	Op::Note {
2189	on: vec![range(3, 5, 5), range(3, 5, 6)],
2190	text: Vec::new(),
2191	},
2192	Op::Forget {
2193	of: vec![
2194	Stub { id: oid(1, 1), placing: Placing::File },
2195	Stub { id: oid(1, 2), placing: Placing::Splice {
2196	left: Some(Anchor::origin(oid(1, 1))),
2197	right: None,
2198	remove: vec![],
2199	len: 5,
2200	} },
2201	Stub { id: oid(2, 9), placing: Placing::Void },
2202	],
2203	reason: b"a key that should never have been written".to_vec(),
2204	time: 1_755_000_010,
2205	},
2206	Op::Forgotten { placing: Placing::Void },
2207	Op::Forgotten { placing: Placing::File },
2208	Op::Forgotten { placing: Placing::Splice {
2209	left: Some(Anchor::origin(oid(1, 1))),
2210	right: None,
2211	remove: vec![],
2212	len: 5,
2213	} },
2214	]
2215	}
2216
2217	/// Headers spanning no parents, one, and many.
2218	fn sample_heads() -> Outcome<Vec<Header>> {
2219	Ok(vec![
2220	Header::root(oid(1, 1)),
2221	res!(Header::new(oid(2, 9), vec![oid(1, 1)])),
2222	res!(Header::new(oid(3, 4), vec![
2223	oid(1, 1),
2224	oid(2, 9),
2225	oid(9, u64::MAX),
2226	])),
2227	res!(Header::new(oid(4, u64::MAX), (1..=200)
2228	.map(\|i\| oid(i % 13, i))
2229	.collect())),
2230	])
2231	}
2232
2233	#[test]
2234	fn op_dat_round_trip() -> Outcome<()> {
2235	for op in samples() {
2236	let back = res!(Op::from_dat(&op.to_dat()));
2237	assert_eq!(op, back, "variant {}", op.name());
2238	}
2239	Ok(())
2240	}
2241
2242	#[test]
2243	fn op_byte_round_trip() -> Outcome<()> {
2244	for op in samples() {
2245	let buf = res!(op.encode());
2246	let back = res!(Op::decode_all(&buf));
2247	assert_eq!(op, back, "variant {}", op.name());
2248	}
2249	Ok(())
2250	}
2251
2252	/// A payload longer than 255 bytes keeps its full length, which a `Dat::BU8`
2253	/// length field could not express.
2254	#[test]
2255	fn payloads_survive_beyond_a_byte_length() -> Outcome<()> {
2256	for len in [255usize, 256, 257, 4096, 70_000] {
2257	let op = Op::Splice {
2258	left: Some(Anchor::origin(oid(1, 1))),
2259	right: None,
2260	remove: Vec::new(),
2261	insert: vec![0x5a; len].into(),
2262	};
2263	let back = res!(Op::decode_all(&res!(op.encode())));
2264	match back {
2265	Op::Splice { insert, .. } => assert_eq!(insert.len(), len),
2266	other => return Err(err!(
2267	"Expected a Splice, got {}.", other.name(); Test, Mismatch)),
2268	}
2269	let op = Op::FileCreate { path: vec![0x2f; len] };
2270	match res!(Op::decode_all(&res!(op.encode()))) {
2271	Op::FileCreate { path } => assert_eq!(path.len(), len),
2272	other => return Err(err!(
2273	"Expected a FileCreate, got {}.", other.name(); Test, Mismatch)),
2274	}
2275	let op = Op::Note {
2276	on: vec![range(1, 0, 1)],
2277	text: vec![0x21; len],
2278	};
2279	match res!(Op::decode_all(&res!(op.encode()))) {
2280	Op::Note { text, .. } => assert_eq!(text.len(), len),
2281	other => return Err(err!(
2282	"Expected a Note, got {}.", other.name(); Test, Mismatch)),
2283	}
2284	}
2285	Ok(())
2286	}
2287
2288	#[test]
2289	fn ops_decode_back_to_back() -> Outcome<()> {
2290	let ops = samples();
2291	let mut buf = Vec::new();
2292	for op in &ops {
2293	res!(op.encode_into(&mut buf));
2294	}
2295	let mut at = 0;
2296	for want in &ops {
2297	let (got, used) = res!(Op::decode(&buf[at..]));
2298	assert_eq!(&got, want);
2299	at += used;
2300	}
2301	assert_eq!(at, buf.len());
2302	Ok(())
2303	}
2304
2305	#[test]
2306	fn codes_are_distinct() -> Outcome<()> {
2307	let mut seen = Vec::new();
2308	for op in samples() {
2309	let code = op.code();
2310	assert!(code != 0, "variant {} has a zero code", op.name());
2311	if !seen.contains(&(code, op.name())) {
2312	seen.push((code, op.name()));
2313	}
2314	}
2315	for (i, (code, name)) in seen.iter().enumerate() {
2316	for (other_code, other_name) in seen.iter().skip(i + 1) {
2317	assert!(
2318	code != other_code,
2319	"{} and {} share code {}", name, other_name, code,
2320	);
2321	}
2322	}
2323	Ok(())
2324	}
2325
2326	#[test]
2327	fn only_a_lifecycle_change_names_a_file() -> Outcome<()> {
2328	assert_eq!(Op::FileDelete { file: oid(3, 1) }.names_file(), Some(oid(3, 1)));
2329	assert_eq!(
2330	Op::FileRename { file: oid(3, 1), path: b"x".to_vec() }.names_file(),
2331	Some(oid(3, 1)),
2332	);
2333	assert_eq!(Op::FileCreate { path: b"c.txt".to_vec() }.names_file(), None,
2334	"a file's creation is its identity, so it names nothing else");
2335	assert_eq!(Op::Mark { name: fmt!("v1"), body: None, time: None }.names_file(), None);
2336	assert_eq!(Op::Note {
2337	on: vec![range(1, 0, 2)],
2338	text: b"x".to_vec(),
2339	}.names_file(), None, "a note follows its content, wherever that is");
2340	assert_eq!(Op::Splice {
2341	left: Some(Anchor::origin(oid(1, 1))),
2342	right: None,
2343	remove: Vec::new(),
2344	insert: b"x".to_vec().into(),
2345	}.names_file(), None);
2346	assert_eq!(Op::Move {
2347	src: Vec::new(),
2348	left: Some(Anchor::origin(oid(1, 1))),
2349	right: None,
2350	}.names_file(), None);
2351	Ok(())
2352	}
2353
2354	#[test]
2355	fn a_placement_names_where_it_lands() -> Outcome<()> {
2356	// A splice inserting bytes with neither origin belongs to no file.
2357	let stray = Op::Splice {
2358	left: None,
2359	right: None,
2360	remove: Vec::new(),
2361	insert: b"x".to_vec().into(),
2362	};
2363	assert!(stray.check_placement().is_err());
2364	assert!(stray.validate().is_err());
2365	// And the decoder refuses it rather than leaving it to a later stage.
2366	assert!(Op::from_dat(&stray.to_dat()).is_err());
2367	assert!(Op::decode_all(&res!(stray.encode())).is_err());
2368	// Either origin alone satisfies the rule.
2369	for (left, right) in [
2370	(Some(Anchor::origin(oid(1, 1))), None),
2371	(None, Some(Anchor::before(content(1, 0)))),
2372	] {
2373	let op = Op::Splice { left, right, remove: Vec::new(), insert: b"x".to_vec().into() };
2374	res!(op.check_placement());
2375	assert_eq!(op, res!(Op::from_dat(&op.to_dat())));
2376	}
2377	// A splice that only removes places nothing and needs no origin.
2378	let del = Op::Splice {
2379	left: None,
2380	right: None,
2381	remove: vec![range(1, 0, 4)],
2382	insert: Vec::new().into(),
2383	};
2384	res!(del.validate());
2385	assert_eq!(del, res!(Op::from_dat(&del.to_dat())));
2386	// A move always places what it names, so it always names where.
2387	let nowhere = Op::Move { src: vec![range(1, 0, 4)], left: None, right: None };
2388	assert!(nowhere.check_placement().is_err());
2389	assert!(Op::from_dat(&nowhere.to_dat()).is_err());
2390	// Even a move of nothing, since the rule is about the operation and not
2391	// about how much it happens to carry.
2392	let empty = Op::Move { src: Vec::new(), left: None, right: None };
2393	assert!(empty.check_placement().is_err());
2394	Ok(())
2395	}
2396
2397	#[test]
2398	fn a_note_is_about_something() -> Outcome<()> {
2399	// An empty list names nothing.
2400	let vacant = Op::Note { on: Vec::new(), text: b"about what?".to_vec() };
2401	assert!(vacant.check_note().is_err());
2402	assert!(vacant.validate().is_err());
2403	assert!(Op::from_dat(&vacant.to_dat()).is_err());
2404	assert!(Op::decode_all(&res!(vacant.encode())).is_err());
2405	// A list of empty ranges names nothing either.
2406	let hollow = Op::Note {
2407	on: vec![range(1, 3, 3), range(2, 0, 0)],
2408	text: b"still nothing".to_vec(),
2409	};
2410	assert!(hollow.check_note().is_err());
2411	assert!(Op::from_dat(&hollow.to_dat()).is_err());
2412	// One byte is enough.
2413	let real = Op::Note {
2414	on: vec![range(1, 3, 3), range(2, 0, 1)],
2415	text: Vec::new(),
2416	};
2417	res!(real.validate());
2418	assert_eq!(real, res!(Op::from_dat(&real.to_dat())));
2419	// And every other variant is unaffected by the rule.
2420	for op in samples() {
2421	if matches!(op, Op::Note { .. }) {
2422	continue;
2423	}
2424	res!(op.check_note());
2425	}
2426	Ok(())
2427	}
2428
2429	/// A note is not among the regions two operations could be in conflict over.
2430	#[test]
2431	fn a_note_refers_without_claiming() -> Outcome<()> {
2432	let note = Op::Note {
2433	on: vec![range(1, 4, 9), range(2, 0, 3)],
2434	text: b"see the ticket".to_vec(),
2435	};
2436	assert!(note.regions().is_empty(), "a note claims nothing");
2437	assert_eq!(note.note_on().len(), 2);
2438	assert_eq!(note.origins(), (None, None));
2439	assert_eq!(note.placed_len(), 0);
2440	assert!(!note.is_move());
2441	res!(note.check_placement());
2442	// The other variants refer to nothing, whatever they claim.
2443	assert!(Op::Move {
2444	src: vec![range(1, 0, 4)],
2445	left: Some(Anchor::origin(oid(9, 1))),
2446	right: None,
2447	}.note_on().is_empty());
2448	assert!(Op::Mark { name: fmt!("v1"), body: None, time: None }.note_on().is_empty());
2449	Ok(())
2450	}
2451
2452	#[test]
2453	fn an_operation_reports_its_origins_and_its_content() -> Outcome<()> {
2454	let mv = Op::Move {
2455	src: vec![range(1, 0, 4), range(2, 0, 6)],
2456	left: Some(Anchor::origin(oid(9, 1))),
2457	right: None,
2458	};
2459	assert_eq!(mv.origins(), (Some(Anchor::origin(oid(9, 1))), None));
2460	assert_eq!(mv.regions().len(), 2);
2461	assert_eq!(mv.placed_len(), 10);
2462	assert!(mv.is_move());
2463	let create = Op::FileCreate { path: b"f".to_vec() };
2464	assert_eq!(create.origins(), (None, None));
2465	assert!(create.regions().is_empty());
2466	assert_eq!(create.placed_len(), 0);
2467	assert!(!create.is_move());
2468	Ok(())
2469	}
2470
2471	/// An origin on the wrong side, or a move naming one byte twice.
2472	#[test]
2473	fn validate_refuses_what_cannot_be_resolved() -> Outcome<()> {
2474	let cid = content(1, 0);
2475	assert!(Op::Splice {
2476	left: Some(Anchor::before(cid)),
2477	right: None,
2478	remove: Vec::new(),
2479	insert: b"x".to_vec().into(),
2480	}.validate().is_err());
2481	assert!(Op::Splice {
2482	left: None,
2483	right: Some(Anchor::after(cid)),
2484	remove: Vec::new(),
2485	insert: b"x".to_vec().into(),
2486	}.validate().is_err());
2487	assert!(Op::Move {
2488	src: vec![range(1, 0, 4), range(1, 2, 6)],
2489	left: Some(Anchor::origin(oid(9, 1))),
2490	right: None,
2491	}.validate().is_err());
2492	Ok(())
2493	}
2494
2495	#[test]
2496	fn a_mode_is_one_of_three_things() -> Outcome<()> {
2497	assert_eq!(Mode::default(), Mode::Normal, "silence means an ordinary file");
2498	assert!(Mode::Normal.is_normal());
2499	assert!(!Mode::Executable.is_normal());
2500	assert!(!Mode::Symlink.is_normal());
2501	let all = [Mode::Normal, Mode::Executable, Mode::Symlink];
2502	for mode in all {
2503	assert_eq!(mode, res!(Mode::from_dat(&mode.to_dat())), "mode {}", mode);
2504	assert_eq!(fmt!("{}", mode), mode.name());
2505	}
2506	// The codes are distinct, and pinned: they are on the wire.
2507	assert_eq!(Mode::Normal.code(), 0);
2508	assert_eq!(Mode::Executable.code(), 1);
2509	assert_eq!(Mode::Symlink.code(), 2);
2510	// A fourth mode is refused rather than guessed at, and so is a spelling
2511	// that is not a number at all.
2512	assert!(Mode::from_dat(&Dat::U8(3)).is_err());
2513	assert!(Mode::from_dat(&Dat::U8(255)).is_err());
2514	assert!(Mode::from_dat(&Dat::Str(fmt!("executable"))).is_err());
2515	assert!(Mode::from_dat(&Dat::U64(1)).is_err());
2516	Ok(())
2517	}
2518
2519	#[test]
2520	fn a_mode_operation_names_a_file() -> Outcome<()> {
2521	for mode in [Mode::Normal, Mode::Executable, Mode::Symlink] {
2522	let op = Op::FileMode { file: oid(3, 1), mode };
2523	assert_eq!(op.code(), CODE_FILE_MODE);
2524	assert_eq!(op.code(), 8, "the wire code is what the event fixed");
2525	assert_eq!(op.name(), "FileMode");
2526	// It is a lifecycle change, so it names its file the way a rename and
2527	// a delete do.
2528	assert_eq!(op.names_file(), Some(oid(3, 1)));
2529	// And it says nothing about content: it places nothing, claims
2530	// nothing and refers to nothing.
2531	assert_eq!(op.origins(), (None, None));
2532	assert!(op.regions().is_empty());
2533	assert!(op.note_on().is_empty());
2534	assert_eq!(op.placed_len(), 0);
2535	assert!(!op.is_move());
2536	res!(op.validate());
2537	assert_eq!(op, res!(Op::from_dat(&op.to_dat())));
2538	assert_eq!(op, res!(Op::decode_all(&res!(op.encode()))));
2539	}
2540	// The arity is exact, as it is everywhere else, and the mode is checked
2541	// on the way off the wire rather than left to a later stage.
2542	assert!(Op::from_dat(&Dat::List(vec![
2543	Dat::U8(CODE_FILE_MODE),
2544	oid(3, 1).to_dat(),
2545	])).is_err());
2546	assert!(Op::from_dat(&Dat::List(vec![
2547	Dat::U8(CODE_FILE_MODE),
2548	oid(3, 1).to_dat(),
2549	Dat::U8(MODE_SYMLINK),
2550	Dat::U8(0),
2551	])).is_err());
2552	assert!(Op::from_dat(&Dat::List(vec![
2553	Dat::U8(CODE_FILE_MODE),
2554	oid(3, 1).to_dat(),
2555	Dat::U8(200),
2556	])).is_err());
2557	// A file named by something that is not an identifier.
2558	assert!(Op::from_dat(&Dat::List(vec![
2559	Dat::U8(CODE_FILE_MODE),
2560	Dat::Str(fmt!("src/lib.rs")),
2561	Dat::U8(MODE_EXECUTABLE),
2562	])).is_err());
2563	Ok(())
2564	}
2565
2566	/// The short spelling is the whole of the compatibility claim: a mark saying
2567	/// nothing beyond its name is [`CODE_MARK`] with two elements, byte for byte
2568	/// what was written before the fields existed, so every mark already signed
2569	/// still verifies.
2570	#[test]
2571	fn a_mark_has_two_spellings_and_one_variant() -> Outcome<()> {
2572	// The short spelling, pinned as a daticle and as bytes.
2573	let plain = Op::Mark { name: fmt!("v1"), body: None, time: None };
2574	assert_eq!(plain.code(), CODE_MARK);
2575	assert_eq!(plain.code(), 4, "the wire code a mark has always had");
2576	assert_eq!(plain.name(), "Mark");
2577	assert_eq!(plain.to_dat(), Dat::List(vec![
2578	Dat::U8(CODE_MARK),
2579	Dat::Str(fmt!("v1")),
2580	]));
2581	assert_eq!(
2582	res!(plain.encode()),
2583	vec![0x0a, 0x33, 0x21, 0x07, 0x0a, 0x04, 0x29, 0x21, 0x02, 0x76, 0x31],
2584	"the bytes of a bodyless, timeless mark have moved",
2585	);
2586	// The long spelling, at every combination that reaches it.
2587	for (body, time) in [
2588	(Some(b"why".to_vec()), None),
2589	(None, Some(1_755_400_329u64)),
2590	(Some(Vec::new()), Some(0)),
2591	] {
2592	let op = Op::Mark { name: fmt!("v1"), body: body.clone(), time };
2593	assert_eq!(op.code(), CODE_MARK_TIMED, "body {:?} time {:?}", body, time);
2594	assert_eq!(op.code(), 9);
2595	assert_eq!(op.name(), "Mark", "one variant, so one name");
2596	match op.to_dat() {
2597	Dat::List(v) => assert_eq!(v.len(), 4, "the long spelling is four"),
2598	other => return Err(err!(
2599	"A Mark encodes to {:?}.", other; Test, Mismatch)),
2600	}
2601	// And back, through both round trips.
2602	assert_eq!(op, res!(Op::from_dat(&op.to_dat())));
2603	assert_eq!(op, res!(Op::decode_all(&res!(op.encode()))));
2604	}
2605	// A code 4 mark and a code 9 mark decode to the same variant.
2606	let short = res!(Op::from_dat(&Dat::List(vec![
2607	Dat::U8(CODE_MARK),
2608	Dat::Str(fmt!("v1")),
2609	])));
2610	let long = res!(Op::from_dat(&Dat::List(vec![
2611	Dat::U8(CODE_MARK_TIMED),
2612	Dat::Str(fmt!("v1")),
2613	Dat::Opt(Box::new(None)),
2614	Dat::Opt(Box::new(Some(Dat::U64(9)))),
2615	])));
2616	assert!(matches!(short, Op::Mark { .. }));
2617	assert!(matches!(long, Op::Mark { .. }));
2618	assert_eq!(short.name(), long.name());
2619	assert_eq!(short, plain);
2620	match (&short, &long) {
2621	(
2622	Op::Mark { name: a, body: None, time: None },
2623	Op::Mark { name: b, body: None, time: Some(9) },
2624	) => assert_eq!(a, b),
2625	_ => return Err(err!(
2626	"The two spellings did not read back as one variant."; Test, Mismatch)),
2627	}
2628	// The arity of each spelling is exact, as it is everywhere else.
2629	assert!(Op::from_dat(&Dat::List(vec![
2630	Dat::U8(CODE_MARK),
2631	Dat::Str(fmt!("v1")),
2632	Dat::Opt(Box::new(None)),
2633	Dat::Opt(Box::new(None)),
2634	])).is_err(), "code 4 takes two elements");
2635	assert!(Op::from_dat(&Dat::List(vec![
2636	Dat::U8(CODE_MARK_TIMED),
2637	Dat::Str(fmt!("v1")),
2638	])).is_err(), "code 9 takes four elements");
2639	// A body is bytes and a time is a number, not the other way about.
2640	assert!(Op::from_dat(&Dat::List(vec![
2641	Dat::U8(CODE_MARK_TIMED),
2642	Dat::Str(fmt!("v1")),
2643	Dat::Opt(Box::new(Some(Dat::Str(fmt!("not bytes"))))),
2644	Dat::Opt(Box::new(None)),
2645	])).is_err());
2646	assert!(Op::from_dat(&Dat::List(vec![
2647	Dat::U8(CODE_MARK_TIMED),
2648	Dat::Str(fmt!("v1")),
2649	Dat::Opt(Box::new(None)),
2650	Dat::Opt(Box::new(Some(Dat::U8(9)))),
2651	])).is_err(), "a time is a Dat::U64 and nothing narrower");
2652	// A bare field where an optional one belongs.
2653	assert!(Op::from_dat(&Dat::List(vec![
2654	Dat::U8(CODE_MARK_TIMED),
2655	Dat::Str(fmt!("v1")),
2656	Dat::BU64(b"why".to_vec()),
2657	Dat::Opt(Box::new(None)),
2658	])).is_err());
2659	// And the long spelling is refused where it says nothing the short one
2660	// could not: an operation has one encoding.
2661	assert!(Op::from_dat(&Dat::List(vec![
2662	Dat::U8(CODE_MARK_TIMED),
2663	Dat::Str(fmt!("v1")),
2664	Dat::Opt(Box::new(None)),
2665	Dat::Opt(Box::new(None)),
2666	])).is_err(), "code 9 carrying neither is code 4 spelled twice");
2667	// A body beyond what a single byte length field could hold keeps its
2668	// length, which is why it is a BU64.
2669	for len in [255usize, 256, 70_000] {
2670	let op = Op::Mark {
2671	name: fmt!("v1"),
2672	body: Some(vec![0x5a; len]),
2673	time: Some(1),
2674	};
2675	match res!(Op::decode_all(&res!(op.encode()))) {
2676	Op::Mark { body: Some(b), .. } => assert_eq!(b.len(), len),
2677	other => return Err(err!(
2678	"Expected a Mark with a body, got {}.", other.name();
2679	Test, Mismatch)),
2680	}
2681	}
2682	Ok(())
2683	}
2684
2685	#[test]
2686	fn the_proposal_operations_round_trip() -> Outcome<()> {
2687	let prop = Op::Proposal {
2688	title: fmt!("Carry a body on a mark"),
2689	body: b"the case for it".to_vec(),
2690	voice: fmt!("wren"),
2691	time: 1_755_400_000,
2692	};
2693	let said = Op::Said {
2694	on: oid(3, 4),
2695	text: b"agreed".to_vec(),
2696	voice: fmt!("caf\u{e9}"),
2697	time: 1_755_400_100,
2698	};
2699	let settled = Op::Settled {
2700	on: oid(3, 4),
2701	state: Settled::Accepted,
2702	mark: Some(oid(9, 2)),
2703	time: 1_755_400_200,
2704	};
2705	let reverts = Op::Reverts { undone: vec![oid(1, 1), oid(2, 9)] };
2706	for (op, code, name) in [
2707	(&prop, CODE_PROPOSAL, "Proposal"),
2708	(&said, CODE_SAID, "Said"),
2709	(&settled, CODE_SETTLED, "Settled"),
2710	(&reverts, CODE_REVERTS, "Reverts"),
2711	] {
2712	assert_eq!(op.code(), code, "variant {}", name);
2713	assert_eq!(op.name(), name);
2714	res!(op.validate());
2715	assert_eq!(*op, res!(Op::from_dat(&op.to_dat())));
2716	assert_eq!(*op, res!(Op::decode_all(&res!(op.encode()))));
2717	}
2718	// The codes are pinned: they are on the wire.
2719	assert_eq!(CODE_PROPOSAL, 10);
2720	assert_eq!(CODE_SAID, 11);
2721	assert_eq!(CODE_SETTLED, 12);
2722	assert_eq!(CODE_REVERTS, 13);
2723	// Every settled state survives, alongside both spellings of the mark that
2724	// closed the proposal.
2725	for state in [Settled::Open, Settled::Accepted, Settled::Declined, Settled::Done] {
2726	for mark in [None, Some(oid(9, 2))] {
2727	let op = Op::Settled { on: oid(3, 4), state, mark, time: 7 };
2728	assert_eq!(op, res!(Op::decode_all(&res!(op.encode()))), "state {}", state);
2729	}
2730	}
2731	// The arities are exact.
2732	assert!(Op::from_dat(&Dat::List(vec![
2733	Dat::U8(CODE_PROPOSAL),
2734	Dat::Str(fmt!("t")),
2735	Dat::BU64(Vec::new()),
2736	Dat::Str(fmt!("v")),
2737	])).is_err());
2738	assert!(Op::from_dat(&Dat::List(vec![
2739	Dat::U8(CODE_REVERTS),
2740	Dat::List(Vec::new()),
2741	Dat::U64(0),
2742	])).is_err());
2743	// A body is bytes and a title is a string, not the other way about.
2744	assert!(Op::from_dat(&Dat::List(vec![
2745	Dat::U8(CODE_PROPOSAL),
2746	Dat::BU64(b"t".to_vec()),
2747	Dat::BU64(Vec::new()),
2748	Dat::Str(fmt!("v")),
2749	Dat::U64(0),
2750	])).is_err());
2751	// A time is a Dat::U64 and nothing narrower.
2752	assert!(Op::from_dat(&Dat::List(vec![
2753	Dat::U8(CODE_SAID),
2754	oid(3, 4).to_dat(),
2755	Dat::BU64(Vec::new()),
2756	Dat::Str(fmt!("v")),
2757	Dat::U8(0),
2758	])).is_err());
2759	// A proposal is named by an identifier, never by a title.
2760	assert!(Op::from_dat(&Dat::List(vec![
2761	Dat::U8(CODE_SAID),
2762	Dat::Str(fmt!("Carry a body on a mark")),
2763	Dat::BU64(Vec::new()),
2764	Dat::Str(fmt!("v")),
2765	Dat::U64(0),
2766	])).is_err());
2767	// A mark is named by an identifier too, and optionally.
2768	assert!(Op::from_dat(&Dat::List(vec![
2769	Dat::U8(CODE_SETTLED),
2770	oid(3, 4).to_dat(),
2771	Dat::U8(SETTLED_DONE),
2772	Dat::Str(fmt!("v1")),
2773	Dat::U64(0),
2774	])).is_err());
2775	assert!(Op::from_dat(&Dat::List(vec![
2776	Dat::U8(CODE_SETTLED),
2777	oid(3, 4).to_dat(),
2778	Dat::U8(SETTLED_DONE),
2779	oid(9, 2).to_dat(),
2780	Dat::U64(0),
2781	])).is_err(), "a bare identifier where an optional one belongs");
2782	Ok(())
2783	}
2784
2785	#[test]
2786	fn a_settled_state_is_one_of_four_things() -> Outcome<()> {
2787	assert_eq!(Settled::default(), Settled::Open, "silence means still asking");
2788	assert!(Settled::Open.is_open());
2789	assert!(!Settled::Accepted.is_open());
2790	for state in [Settled::Open, Settled::Accepted, Settled::Declined, Settled::Done] {
2791	assert_eq!(state, res!(Settled::from_dat(&state.to_dat())), "state {}", state);
2792	assert_eq!(fmt!("{}", state), state.name());
2793	}
2794	// The codes are distinct, and pinned: they are on the wire.
2795	assert_eq!(Settled::Open.code(), 0);
2796	assert_eq!(Settled::Accepted.code(), 1);
2797	assert_eq!(Settled::Declined.code(), 2);
2798	assert_eq!(Settled::Done.code(), 3);
2799	// A fifth state is refused rather than guessed at, and so is a spelling
2800	// that is not a number at all.
2801	assert!(Settled::from_dat(&Dat::U8(4)).is_err());
2802	assert!(Settled::from_dat(&Dat::U8(255)).is_err());
2803	assert!(Settled::from_dat(&Dat::Str(fmt!("accepted"))).is_err());
2804	assert!(Settled::from_dat(&Dat::U64(1)).is_err());
2805	// And an operation carrying one is refused with it.
2806	assert!(Op::from_dat(&Dat::List(vec![
2807	Dat::U8(CODE_SETTLED),
2808	oid(3, 4).to_dat(),
2809	Dat::U8(4),
2810	Dat::Opt(Box::new(None)),
2811	Dat::U64(0),
2812	])).is_err());
2813	Ok(())
2814	}
2815
2816	/// A settlement is exactly five wire elements, and nothing more may be added to
2817	/// it.
2818	///
2819	/// This is a load-bearing invariant, not a formality. [`Op::from_dat`] validates
2820	/// the length with [`expect_len`], so a six-element settlement is refused by every
2821	/// reader written against this format -- including the external cloners of a public
2822	/// repository still running an older client. An acceptance reason therefore rides
2823	/// as a separate [`Op::Said`] rather than a sixth field here; if this test ever has
2824	/// to change to add one, so does every one of those readers first.
2825	#[test]
2826	fn a_settlement_is_five_wire_elements() -> Outcome<()> {
2827	let op = Op::Settled {
2828	on: oid(3, 4),
2829	state: Settled::Accepted,
2830	mark: None,
2831	time: 7,
2832	};
2833	let dat = op.to_dat();
2834	let listed = match &dat {
2835	Dat::List(v) => v,
2836	other => return Err(err!(
2837	"A settlement serialises to a list, got {:?}.", other; Test, Mismatch)),
2838	};
2839	assert_eq!(listed.len(), 5, "a settlement grew or lost a wire element");
2840	assert_eq!(listed[0], Dat::U8(CODE_SETTLED));
2841	assert_eq!(op, res!(Op::from_dat(&dat)), "a settlement did not round-trip");
2842	// A sixth element is refused, which is the whole point: adding a field would
2843	// break this and every reader like it.
2844	let mut six = listed.clone();
2845	six.push(Dat::Str(fmt!("a reason")));
2846	assert!(Op::from_dat(&Dat::List(six)).is_err(),
2847	"a six-element settlement was accepted, so old readers would break silently");
2848	Ok(())
2849	}
2850
2851	/// The ordering rule is [`Header`]'s parents, for the same reason: two byte
2852	/// spellings of one set would both verify against a signature. The rule that
2853	/// it names anything at all is [`Op::check_note`]'s, for the same reason: a
2854	/// revert of nothing is a mark with extra spelling.
2855	#[test]
2856	fn a_revert_names_what_it_undoes_once_in_order() -> Outcome<()> {
2857	// In order, with no repetition, at every length above nothing.
2858	for undone in [
2859	vec![oid(1, 1)],
2860	vec![oid(1, 1), oid(1, 2), oid(2, 1), oid(9, u64::MAX)],
2861	] {
2862	let op = Op::Reverts { undone: undone.clone() };
2863	res!(op.check_reverts());
2864	res!(op.validate());
2865	assert_eq!(op, res!(Op::from_dat(&op.to_dat())));
2866	assert_eq!(op, res!(Op::decode_all(&res!(op.encode()))));
2867	}
2868	// Naming nothing, out of order, and repeated, on the way into the structure
2869	// and on the way off the wire alike.
2870	for undone in [
2871	Vec::new(),
2872	vec![oid(2, 1), oid(1, 1)],
2873	vec![oid(1, 2), oid(1, 1)],
2874	vec![oid(1, 1), oid(1, 1)],
2875	vec![oid(1, 1), oid(2, 1), oid(2, 1)],
2876	] {
2877	let op = Op::Reverts { undone: undone.clone() };
2878	assert!(op.check_reverts().is_err(), "list {:?}", undone);
2879	assert!(op.validate().is_err());
2880	assert!(Op::from_dat(&op.to_dat()).is_err());
2881	assert!(Op::decode_all(&res!(op.encode())).is_err());
2882	}
2883	// An empty list is refused for saying nothing, not for being out of order,
2884	// so the message sends its author to the operation that does say something
2885	// about a point in history.
2886	let vacant = Op::Reverts { undone: Vec::new() };
2887	let e = match vacant.check_reverts() {
2888	Ok(()) => return Err(err!(
2889	"A Reverts naming nothing was accepted."; Test)),
2890	Err(e) => e,
2891	};
2892	let msg = fmt!("{}", e);
2893	assert!(msg.contains("Mark"), "message was {}", msg);
2894	// Every other variant is unaffected by the rule.
2895	for op in samples() {
2896	if matches!(op, Op::Reverts { .. }) {
2897	continue;
2898	}
2899	res!(op.check_reverts());
2900	}
2901	// What it names are identifiers, not names.
2902	assert!(Op::from_dat(&Dat::List(vec![
2903	Dat::U8(CODE_REVERTS),
2904	Dat::List(vec![Dat::Str(fmt!("v1"))]),
2905	])).is_err());
2906	assert!(Op::from_dat(&Dat::List(vec![
2907	Dat::U8(CODE_REVERTS),
2908	Dat::Str(fmt!("not a list")),
2909	])).is_err());
2910	Ok(())
2911	}
2912
2913	/// This is what every catch-all arm in [`crate::seq`] is relying on: an
2914	/// operation that mints no atom and claims no byte is carried for the sake
2915	/// of the causal graph and does nothing to the render.
2916	#[test]
2917	fn the_history_operations_touch_no_bytes() -> Outcome<()> {
2918	for op in samples() {
2919	match op {
2920	Op::Mark { .. }
2921	\| Op::Note { .. }
2922	\| Op::Proposal { .. }
2923	\| Op::Said { .. }
2924	\| Op::Settled { .. }
2925	\| Op::Reverts { .. } => (),
2926	_ => continue,
2927	}
2928	assert_eq!(op.origins(), (None, None), "variant {}", op.name());
2929	assert!(op.regions().is_empty(), "variant {} claims content", op.name());
2930	assert_eq!(op.placed_len(), 0, "variant {} places bytes", op.name());
2931	assert!(!op.is_move());
2932	assert_eq!(op.names_file(), None, "variant {} names a file", op.name());
2933	res!(op.check_placement());
2934	// Only a note refers to content, and it is the one that resolves into
2935	// spans; the rest refer to operations or to nothing.
2936	if !matches!(op, Op::Note { .. }) {
2937	assert!(op.note_on().is_empty(), "variant {} refers to content", op.name());
2938	res!(op.check_note());
2939	}
2940	}
2941	Ok(())
2942	}
2943
2944	#[test]
2945	fn op_from_dat_rejects_rubbish() -> Outcome<()> {
2946	assert!(Op::from_dat(&Dat::U8(CODE_MARK)).is_err());
2947	assert!(Op::from_dat(&Dat::List(vec![])).is_err());
2948	assert!(Op::from_dat(&Dat::List(vec![Dat::U8(200), Dat::Str(fmt!("x"))])).is_err());
2949	// Right code, wrong arity.
2950	assert!(Op::from_dat(&Dat::List(vec![Dat::U8(CODE_FILE_RENAME)])).is_err());
2951	// Right arity, wrong field kind: a path that is a string rather than
2952	// bytes, which is exactly what the old vocabulary spelled.
2953	assert!(Op::from_dat(&Dat::List(vec![
2954	Dat::U8(CODE_FILE_CREATE),
2955	Dat::Str(fmt!("src/lib.rs")),
2956	])).is_err());
2957	// A file named by something that is not an identifier.
2958	assert!(Op::from_dat(&Dat::List(vec![
2959	Dat::U8(CODE_FILE_DELETE),
2960	Dat::Str(fmt!("src/lib.rs")),
2961	])).is_err());
2962	// A Splice whose payload is not a byte vector.
2963	assert!(Op::from_dat(&Dat::List(vec![
2964	Dat::U8(CODE_SPLICE),
2965	Anchor::opt_to_dat(&Some(Anchor::origin(oid(1, 1)))),
2966	Anchor::opt_to_dat(&None),
2967	Dat::List(vec![]),
2968	Dat::Str(fmt!("not bytes")),
2969	])).is_err());
2970	// A Splice whose removed runs are not ranges.
2971	assert!(Op::from_dat(&Dat::List(vec![
2972	Dat::U8(CODE_SPLICE),
2973	Anchor::opt_to_dat(&None),
2974	Anchor::opt_to_dat(&None),
2975	Dat::Str(fmt!("not ranges")),
2976	Dat::BU64(Vec::new()),
2977	])).is_err());
2978	// A Move whose source is not a list of ranges.
2979	assert!(Op::from_dat(&Dat::List(vec![
2980	Dat::U8(CODE_MOVE),
2981	Dat::Str(fmt!("not ranges")),
2982	Anchor::opt_to_dat(&Some(Anchor::origin(oid(1, 1)))),
2983	Anchor::opt_to_dat(&None),
2984	])).is_err());
2985	// A Move whose anchor is bare rather than optional.
2986	assert!(Op::from_dat(&Dat::List(vec![
2987	Dat::U8(CODE_MOVE),
2988	Dat::List(vec![range(1, 0, 2).to_dat()]),
2989	Anchor::after(content(1, 0)).to_dat(),
2990	Anchor::opt_to_dat(&None),
2991	])).is_err());
2992	// A Note at the wrong arity.
2993	assert!(Op::from_dat(&Dat::List(vec![
2994	Dat::U8(CODE_NOTE),
2995	Dat::List(vec![range(1, 0, 2).to_dat()]),
2996	])).is_err());
2997	// A Note whose subject is not a list of ranges.
2998	assert!(Op::from_dat(&Dat::List(vec![
2999	Dat::U8(CODE_NOTE),
3000	Dat::Str(fmt!("not ranges")),
3001	Dat::BU64(b"text".to_vec()),
3002	])).is_err());
3003	// A Note whose text is a string rather than bytes, which is the mistake a
3004	// reader of Op::Mark would make.
3005	assert!(Op::from_dat(&Dat::List(vec![
3006	Dat::U8(CODE_NOTE),
3007	Dat::List(vec![range(1, 0, 2).to_dat()]),
3008	Dat::Str(fmt!("not bytes")),
3009	])).is_err());
3010	Ok(())
3011	}
3012
3013	#[test]
3014	fn move_keeps_its_source_runs_in_order() -> Outcome<()> {
3015	let src: Vec<ContentRange> = (0..300u64)
3016	.map(\|i\| range(i % 7 + 1, i, i + 5))
3017	.collect();
3018	let op = Op::Move {
3019	src: src.clone(),
3020	left: Some(Anchor::after(content(1, 9))),
3021	right: None,
3022	};
3023	for back in [
3024	res!(Op::from_dat(&op.to_dat())),
3025	res!(Op::decode_all(&res!(op.encode()))),
3026	] {
3027	match back {
3028	Op::Move { src: got, .. } => assert_eq!(got, src),
3029	other => return Err(err!(
3030	"Expected a Move, got {}.", other.name(); Test, Mismatch)),
3031	}
3032	}
3033	Ok(())
3034	}
3035
3036	/// The side decides whether an insertion abutting the moved run travels with
3037	/// it.
3038	#[test]
3039	fn move_anchors_keep_their_side() -> Outcome<()> {
3040	let cid = content(2, 11);
3041	for (left, right) in [
3042	(Some(Anchor::after(cid)), None),
3043	(None, Some(Anchor::before(cid))),
3044	(Some(Anchor::after(cid)), Some(Anchor::before(cid))),
3045	// The sides the sequence structure refuses are still spelled
3046	// faithfully; refusing them is the structure's business, not the
3047	// codec's. What the codec does refuse is an operation carrying no
3048	// origin at all, which belongs to no file.
3049	(Some(Anchor::before(cid)), Some(Anchor::after(cid))),
3050	] {
3051	let op = Op::Move {
3052	src: vec![range(1, 0, 3)],
3053	left,
3054	right,
3055	};
3056	assert_eq!(op, res!(Op::decode_all(&res!(op.encode()))));
3057	assert_eq!(op, res!(Op::from_dat(&op.to_dat())));
3058	// A splice carrying the same origins spells them the same way.
3059	let sp = Op::Splice {
3060	left,
3061	right,
3062	remove: vec![range(1, 0, 3)],
3063	insert: b"x".to_vec().into(),
3064	};
3065	assert_eq!(sp, res!(Op::decode_all(&res!(sp.encode()))));
3066	assert_eq!(sp, res!(Op::from_dat(&sp.to_dat())));
3067	}
3068	Ok(())
3069	}
3070
3071	/// Under the identity hasher the result is exactly the canonical encoding.
3072	#[test]
3073	fn op_hashes_its_canonical_encoding() -> Outcome<()> {
3074	let op = sample_op_for_hashing();
3075	let want = res!(op.encode());
3076	let got = res!(op.hash((), [0u8; 0])).as_vec();
3077	assert_eq!(got, want);
3078	// An operation differing in one field hashes differently.
3079	let other = Op::Splice {
3080	left: None,
3081	right: None,
3082	remove: vec![range(1, 12, 16)],
3083	insert: Vec::new().into(),
3084	};
3085	assert!(res!(other.hash((), [0u8; 0])).as_vec() != want);
3086	Ok(())
3087	}
3088
3089	fn sample_op_for_hashing() -> Op {
3090	Op::Splice {
3091	left: None,
3092	right: None,
3093	remove: vec![range(1, 12, 15)],
3094	insert: Vec::new().into(),
3095	}
3096	}
3097
3098	#[test]
3099	fn op_decode_rejects_truncation() -> Outcome<()> {
3100	let op = Op::Splice {
3101	left: Some(Anchor::after(content(1, 0))),
3102	right: None,
3103	remove: vec![range(1, 1, 3)],
3104	insert: b"abcdef".to_vec().into(),
3105	};
3106	let buf = res!(op.encode());
3107	for cut in 1..buf.len() {
3108	assert!(Op::decode(&buf[..cut]).is_err(), "cut at {}", cut);
3109	}
3110	let note = Op::Note {
3111	on: vec![range(1, 1, 3), range(2, 0, 8)],
3112	text: b"a note that is cut short".to_vec(),
3113	};
3114	let buf = res!(note.encode());
3115	for cut in 1..buf.len() {
3116	assert!(Op::decode(&buf[..cut]).is_err(), "note cut at {}", cut);
3117	}
3118	Ok(())
3119	}
3120
3121	#[test]
3122	fn header_round_trips_at_every_arity() -> Outcome<()> {
3123	for head in res!(sample_heads()) {
3124	assert_eq!(head, res!(Header::from_dat(&head.to_dat())));
3125	let rec = Record::new(head.clone(), Op::Mark { name: fmt!("m"), body: None, time: None });
3126	assert_eq!(rec, res!(Record::decode_all(&res!(rec.encode()))));
3127	}
3128	Ok(())
3129	}
3130
3131	/// The same frontier given in any order has one encoding.
3132	#[test]
3133	fn parents_are_canonical() -> Outcome<()> {
3134	let a = res!(Header::new(oid(9, 1), vec![oid(1, 2), oid(3, 1), oid(1, 2)]));
3135	let b = res!(Header::new(oid(9, 1), vec![oid(3, 1), oid(1, 2)]));
3136	assert_eq!(a, b);
3137	assert_eq!(a.parents(), &[oid(1, 2), oid(3, 1)]);
3138	assert_eq!(a.id(), oid(9, 1));
3139	assert_eq!(res!(a.to_dat().to_bytes(Vec::new())), res!(b.to_dat().to_bytes(Vec::new())));
3140	// The decoder refuses the non-canonical spellings the constructor fixes.
3141	let unsorted = Dat::List(vec![
3142	oid(9, 1).to_dat(),
3143	Dat::List(vec![oid(3, 1).to_dat(), oid(1, 2).to_dat()]),
3144	]);
3145	assert!(Header::from_dat(&unsorted).is_err());
3146	let repeated = Dat::List(vec![
3147	oid(9, 1).to_dat(),
3148	Dat::List(vec![oid(1, 2).to_dat(), oid(1, 2).to_dat()]),
3149	]);
3150	assert!(Header::from_dat(&repeated).is_err());
3151	Ok(())
3152	}
3153
3154	#[test]
3155	fn an_operation_is_not_its_own_parent() -> Outcome<()> {
3156	assert!(Header::new(oid(1, 4), vec![oid(2, 1), oid(1, 4)]).is_err());
3157	let itself = Dat::List(vec![
3158	oid(1, 4).to_dat(),
3159	Dat::List(vec![oid(1, 4).to_dat()]),
3160	]);
3161	assert!(Header::from_dat(&itself).is_err());
3162	Ok(())
3163	}
3164
3165	#[test]
3166	fn a_root_header_has_no_parents() -> Outcome<()> {
3167	let head = Header::root(oid(1, 1));
3168	assert!(head.is_root());
3169	assert!(head.parents().is_empty());
3170	assert!(!res!(Header::new(oid(1, 2), vec![oid(1, 1)])).is_root());
3171	Ok(())
3172	}
3173
3174	#[test]
3175	fn record_round_trips_every_variant() -> Outcome<()> {
3176	let head = res!(Header::new(oid(5, 7), vec![oid(1, 1), oid(2, 2)]));
3177	for op in samples() {
3178	let rec = Record::new(head.clone(), op);
3179	assert_eq!(rec, res!(Record::from_dat(&rec.to_dat())));
3180	assert_eq!(rec, res!(Record::decode_all(&res!(rec.encode()))));
3181	}
3182	assert!(Record::from_dat(&Dat::U8(1)).is_err());
3183	assert!(Record::from_dat(&Dat::List(vec![Dat::U8(1)])).is_err());
3184	Ok(())
3185	}
3186
3187	#[test]
3188	fn the_parents_are_covered_by_the_hash() -> Outcome<()> {
3189	let op = Op::Mark { name: fmt!("v1"), body: None, time: None };
3190	let one = Record::new(res!(Header::new(oid(1, 5), vec![oid(2, 1)])), op.clone());
3191	let two = Record::new(res!(Header::new(oid(1, 5), vec![oid(2, 2)])), op);
3192	assert!(
3193	res!(one.hash((), [0u8; 0])).as_vec() != res!(two.hash((), [0u8; 0])).as_vec(),
3194	"re-parenting must change the hash",
3195	);
3196	Ok(())
3197	}
3198
3199	#[test]
3200	fn record_decode_rejects_truncation() -> Outcome<()> {
3201	let rec = Record::new(
3202	res!(Header::new(oid(2, 3), vec![oid(1, 1), oid(1, 2)])),
3203	Op::Splice {
3204	left: Some(Anchor::origin(oid(1, 1))),
3205	right: None,
3206	remove: Vec::new(),
3207	insert: b"abcdef".to_vec().into(),
3208	},
3209	);
3210	let buf = res!(rec.encode());
3211	for cut in 1..buf.len() {
3212	assert!(Record::decode(&buf[..cut]).is_err(), "cut at {}", cut);
3213	}
3214	Ok(())
3215	}
3216
3217	#[test]
3218	fn records_decode_back_to_back() -> Outcome<()> {
3219	let heads = res!(sample_heads());
3220	let recs: Vec<Record> = samples()
3221	.into_iter()
3222	.enumerate()
3223	.map(\|(i, op)\| Record::new(heads[i % heads.len()].clone(), op))
3224	.collect();
3225	let mut buf = Vec::new();
3226	for rec in &recs {
3227	res!(rec.encode_into(&mut buf));
3228	}
3229	let mut at = 0;
3230	for want in &recs {
3231	let (got, used) = res!(Record::decode(&buf[at..]));
3232	assert_eq!(&got, want);
3233	at += used;
3234	}
3235	assert_eq!(at, buf.len());
3236	Ok(())
3237	}
3238
3239	/// By one character and by nothing else: what a tool spells after the prefix
3240	/// is that tool's business, and two of them may spell it differently.
3241	#[test]
3242	fn a_mark_a_tool_wrote_is_known_by_its_first_character() -> Outcome<()> {
3243	assert!(is_auto_mark("@2026-08-17T04:12:09.482913Z"));
3244	assert!(is_auto_mark("@"), "the prefix alone is still the prefix");
3245	assert!(is_auto_mark("@whatever a tool likes to spell"),
3246	"nothing after the prefix is read");
3247
3248	assert!(!is_auto_mark("release 1.0"));
3249	assert!(!is_auto_mark(""), "a nameless mark is nobody's automatic one");
3250	assert!(!is_auto_mark("2026-08-17T04:12:09Z"),
3251	"a datetime is not the convention; the prefix is");
3252	assert!(!is_auto_mark(" @2026-08-17T04:12:09Z"),
3253	"the character begins the name or it does not count");
3254
3255	// And through an operation, which is how every consumer meets one.
3256	let op = Op::Mark {
3257	name: fmt!("{}2026-08-17T04:12:09.482913Z", AUTO_MARK_PREFIX),
3258	body: None,
3259	time: Some(1_755_403_929),
3260	};
3261	match &op {
3262	Op::Mark { name, .. } => assert!(is_auto_mark(name)),
3263	other => return Err(err!(
3264	"A mark decoded as {}.", other.name(); Test, Mismatch)),
3265	}
3266	// It carries a time, so it is the four element spelling.
3267	assert_eq!(op.code(), CODE_MARK_TIMED);
3268	Ok(())
3269	}
3270
3271	/// This is what stops a new operation joining the vocabulary and being
3272	/// silently undoable by nothing: [`Op::undoing`] ends on an arm that fails,
3273	/// so the pair of answers has to stay exhaustive.
3274	#[test]
3275	fn every_operation_is_undone_or_says_why_not() -> Outcome<()> {
3276	let refused = [
3277	CODE_FILE_DELETE, CODE_MARK, CODE_MARK_TIMED, CODE_NOTE,
3278	CODE_PROPOSAL, CODE_SAID, CODE_SETTLED, CODE_REVERTS,
3279	CODE_AMENDED, CODE_FORGET, CODE_FORGOTTEN,
3280	];
3281	for op in samples() {
3282	let id = oid(77, 3);
3283	match op.no_inverse() {
3284	Some(why) => {
3285	assert!(refused.contains(&op.code()),
3286	"the {} at code {} refuses an inverse", op.name(), op.code());
3287	// The refusal says why, and the sentence reaches whoever asked.
3288	assert!(why.len() > 20, "the {} gives no reason", op.name());
3289	let e = match op.undoing(id) {
3290	Ok(_) => return Err(err!(
3291	"The {} was undone though nothing undoes it.", op.name(); Test)),
3292	Err(e) => e,
3293	};
3294	assert!(fmt!("{}", e).contains(why),
3295	"the {} refuses without saying why", op.name());
3296	},
3297	None => {
3298	assert!(!refused.contains(&op.code()),
3299	"the {} at code {} has an inverse", op.name(), op.code());
3300	let undoing = res!(op.undoing(id));
3301	// An inverse that is nothing at all would be a silent refusal,
3302	// which is the failure this pair of answers exists to prevent.
3303	assert!(
3304	!undoing.written.is_empty()
3305	\|\| !undoing.copies.is_empty()
3306	\|\| undoing.prior.is_some(),
3307	"the {} is undone by nothing at all", op.name());
3308	for inverse in &undoing.written {
3309	res!(inverse.validate());
3310	}
3311	},
3312	}
3313	}
3314	Ok(())
3315	}
3316
3317	/// Only one half is exact. The insertion is named by the operation that made
3318	/// it, so its inverse names that identity and no render is needed; what the
3319	/// splice removed can come back only as a copy.
3320	#[test]
3321	fn a_splice_is_undone_in_two_halves() -> Outcome<()> {
3322	let id = oid(5, 12);
3323	// A replacement: it inserted five bytes and killed two runs.
3324	let op = Op::Splice {
3325	left: Some(Anchor::after(content(1, 3))),
3326	right: None,
3327	remove: vec![range(1, 4, 9), range(2, 0, 2)],
3328	insert: b"hello".to_vec().into(),
3329	};
3330	let undoing = res!(op.undoing(id));
3331	assert_eq!(undoing.prior, None, "a splice records everything its inverse needs");
3332	assert_eq!(undoing.copies, vec![range(1, 4, 9), range(2, 0, 2)]);
3333	// The insertion half names the atom the splice minted, whole, and inserts
3334	// nothing, so it carries no origin and needs none.
3335	assert_eq!(undoing.written, vec![Op::Splice {
3336	left: None,
3337	right: None,
3338	remove: vec![res!(ContentRange::new(id, 0, 5))],
3339	insert: Vec::new().into(),
3340	}]);
3341	res!(undoing.written[0].validate());
3342
3343	// A pure insertion has an exact inverse and nothing to copy.
3344	let op = Op::Splice {
3345	left: Some(Anchor::origin(oid(1, 1))),
3346	right: None,
3347	remove: Vec::new(),
3348	insert: b"abc".to_vec().into(),
3349	};
3350	let undoing = res!(op.undoing(id));
3351	assert!(undoing.copies.is_empty(), "an insertion buried nothing");
3352	assert_eq!(undoing.written.len(), 1);
3353
3354	// A pure deletion minted no atom, so there is nothing to remove and the
3355	// whole of its inverse is copies.
3356	let op = Op::Splice {
3357	left: None,
3358	right: None,
3359	remove: vec![range(1, 4, 9)],
3360	insert: Vec::new().into(),
3361	};
3362	let undoing = res!(op.undoing(id));
3363	assert!(undoing.written.is_empty(), "a deletion minted nothing to take back");
3364	assert_eq!(undoing.copies, vec![range(1, 4, 9)]);
3365
3366	// An empty run in a remove list names no byte, so it is not a copy owed.
3367	let op = Op::Splice {
3368	left: None,
3369	right: None,
3370	remove: vec![range(1, 4, 4), range(1, 6, 8)],
3371	insert: Vec::new().into(),
3372	};
3373	assert_eq!(res!(op.undoing(id)).copies, vec![range(1, 6, 8)]);
3374	Ok(())
3375	}
3376
3377	#[test]
3378	fn undoing_an_assertion_asks_the_state_it_replaced() -> Outcome<()> {
3379	let file = oid(2, 5);
3380	let undoing = res!(Op::FileRename { file, path: b"b.txt".to_vec() }
3381	.undoing(oid(3, 1)));
3382	assert_eq!(undoing.prior, Some(Prior::Path { file }));
3383	assert!(undoing.written.is_empty() && undoing.copies.is_empty());
3384
3385	let undoing = res!(Op::FileMode { file, mode: Mode::Executable }
3386	.undoing(oid(3, 2)));
3387	assert_eq!(undoing.prior, Some(Prior::Mode { file }));
3388
3389	let undoing = res!(Op::Move {
3390	src: vec![range(1, 0, 4), range(1, 9, 9), range(2, 2, 6)],
3391	left: Some(Anchor::after(content(3, 0))),
3392	right: None,
3393	}.undoing(oid(3, 3)));
3394	// The empty run is dropped: it names no byte, so it has no former place.
3395	assert_eq!(undoing.prior, Some(Prior::Place {
3396	src: vec![range(1, 0, 4), range(2, 2, 6)],
3397	}));
3398
3399	// A file's creation is the one that needs nothing looked up, the file
3400	// having had no prior state at all. It is also the one undoing that cannot
3401	// itself be undone, a deletion having no inverse.
3402	let made = oid(4, 1);
3403	let undoing = res!(Op::FileCreate { path: b"a.txt".to_vec() }.undoing(made));
3404	assert_eq!(undoing.prior, None);
3405	assert_eq!(undoing.written, vec![Op::FileDelete { file: made }]);
3406	assert!(undoing.written[0].no_inverse().is_some(),
3407	"undoing a creation is a one way journey and the vocabulary should say so");
3408	Ok(())
3409	}
3410
3411	/// The anchor is the only record connecting a copy to the writing it is a
3412	/// copy of: the bytes take a new identity the moment they come back, so an
3413	/// accounting that read only the identity would credit whoever reverted.
3414	#[test]
3415	fn a_copy_says_what_it_is_a_copy_of() -> Outcome<()> {
3416	for was in [range(1, 0, 5), range(1, 4, 9), range(7, 0, 1)] {
3417	let bytes = vec![b'x'; was.len() as usize];
3418	let op = res!(Op::restoring(&was, bytes.clone()));
3419	res!(op.validate());
3420	// It binds after the last byte of the run, which is where the run is
3421	// buried, whatever became of what used to surround it.
3422	assert_eq!(op.origins().0, Some(Anchor::after(
3423	ContentId::new(was.op(), was.to() - 1))));
3424	assert_eq!(op.origins().1, None);
3425	assert!(op.regions().is_empty(), "a restoration kills nothing");
3426	assert_eq!(op.restored(), Some(was), "the range {}", was);
3427	// And it survives the wire, which is where a reader meets it.
3428	assert_eq!(res!(Op::from_dat(&op.to_dat())).restored(), Some(was));
3429	}
3430	// A copy of nothing, and a copy of the wrong length, are refused: a
3431	// restoration puts back what was there.
3432	assert!(Op::restoring(&range(1, 4, 4), Vec::new()).is_err());
3433	assert!(Op::restoring(&range(1, 4, 9), b"abc".to_vec()).is_err());
3434	assert!(Op::restoring(&range(1, 4, 9), Vec::new()).is_err());
3435
3436	// Nothing else answers. A splice that removes, one bounded on the right,
3437	// and one anchored before a byte are all ordinary edits.
3438	for op in [
3439	Op::Splice {
3440	left: Some(Anchor::after(content(1, 4))),
3441	right: None,
3442	remove: vec![range(2, 0, 1)],
3443	insert: b"ab".to_vec().into(),
3444	},
3445	Op::Splice {
3446	left: Some(Anchor::after(content(1, 4))),
3447	right: Some(Anchor::before(content(2, 0))),
3448	remove: Vec::new(),
3449	insert: b"ab".to_vec().into(),
3450	},
3451	Op::Splice {
3452	left: None,
3453	right: Some(Anchor::before(content(2, 0))),
3454	remove: Vec::new(),
3455	insert: b"ab".to_vec().into(),
3456	},
3457	] {
3458	assert_eq!(op.restored(), None, "the {} answered", op.name());
3459	}
3460	for op in samples() {
3461	if !matches!(op, Op::Splice { .. }) {
3462	assert_eq!(op.restored(), None, "the {} answered", op.name());
3463	}
3464	}
3465	// A copy longer than the offset it is anchored at names a run reaching
3466	// back past the start of its own atom, which nothing ever wrote.
3467	assert_eq!(Op::Splice {
3468	left: Some(Anchor::after(content(1, 1))),
3469	right: None,
3470	remove: Vec::new(),
3471	insert: b"abcdef".to_vec().into(),
3472	}.restored(), None);
3473	Ok(())
3474	}
3475	}