Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_ore/src/id.rs

28.7 KiB, 155 runs

created by r1870400018:17505, 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//! Identifiers for replicas, for the operations they author, and for the bytes
2//! those operations create.
3//!
4//! An operation is named by the replica that authored it together with that
5//! replica's own counter. A name can therefore be minted without consulting any
6//! other replica and without reading a clock, which is what lets history be
7//! written offline and merged later. Names are unique across replicas, stable
8//! once minted, and totally ordered within a replica.
9//!
10//! Identifiers are encoded as a pair of LEB128-style varints, so a small
11//! replica number and a small counter cost two bytes. The decoder rejects
12//! overlong encodings, giving every identifier exactly one byte spelling --
13//! necessary where those bytes are hashed or signed.
14//!
15//! # Content is named, not located
16//!
17//! Above the operation identifier sit three more names, and none of them is
18//! minted: each is arithmetic over an operation identifier and an offset. A
19//! [`ContentId`] names one byte by the splice that created it, a
20//! [`ContentRange`] names a run of them, and an [`Anchor`] names a gap by the
21//! byte on one side of it. Because a byte's name says what created it rather
22//! than where it sits, the name survives the byte being moved, and an edit
23//! anchored to it travels with the content it was written against.
24//!
25//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
26//! Anthropic Claude
27
28use oxedyne_fe2o3_core::prelude::*;
29use oxedyne_fe2o3_jdat::prelude::*;
30
31use std::fmt;
32use std::ops::Range;
33
34
35pub const VARINT_MAX_LEN: usize = 10; // bytes a u64 varint may occupy
36
37
38/// Each byte carries seven value bits, least significant group first, with the
39/// high bit set on every byte but the last.
40pub fn varint_encode(n: u64, buf: &mut Vec<u8>) {
41 let mut v = n;
42 loop {
43 let byte = (v & 0x7f) as u8;
44 v >>= 7;
45 if v == 0 {
46 buf.push(byte);
47 return;
48 }
49 buf.push(byte | 0x80);
50 }
51}
52
53/// Yields the value and how many bytes it took.
54///
55/// Overlong encodings are rejected so that every value has exactly one byte
56/// spelling. Two spellings of one value would otherwise both verify against a
57/// signature, which is not a property a provenance chain can afford.
58pub fn varint_decode(buf: &[u8])
59 -> Outcome<(u64, usize)>
60{
61 let mut result: u64 = 0;
62 let mut shift: u32 = 0;
63 for (i, byte) in buf.iter().enumerate() {
64 if i >= VARINT_MAX_LEN {
65 return Err(err!(
66 "A varint encoding a u64 occupies at most {} bytes, byte {} continues \
67 beyond that.", VARINT_MAX_LEN, i;
68 Decode, Input, Excessive));
69 }
70 let payload = (*byte & 0x7f) as u64;
71 // The tenth byte of a maximal encoding carries only the top bit of the u64.
72 if i == VARINT_MAX_LEN - 1 && payload > 1 {
73 return Err(err!(
74 "Varint byte {} is {:#04x}, which overflows a u64.", i, byte;
75 Decode, Input, Overflow));
76 }
77 result |= payload << shift;
78 if *byte & 0x80 == 0 {
79 // Only the single byte encoding of zero may end in a zero payload; anything
80 // longer that does so is an overlong spelling of a smaller value.
81 if i > 0 && payload == 0 {
82 return Err(err!(
83 "Varint of {} bytes ends in a zero payload byte, an overlong \
84 encoding.", i + 1;
85 Decode, Input, Invalid));
86 }
87 return Ok((result, i + 1));
88 }
89 shift += 7;
90 }
91 Err(err!(
92 "Varint is truncated: all {} available byte{} carry the continuation bit.",
93 buf.len(), if buf.len() == 1 { "" } else { "s" };
94 Decode, Input, Missing))
95}
96
97
98/// Identifies one writer of history.
99///
100/// A replica is whatever mints operation counters independently: a working
101/// copy, a device, a server-side session. The number carries no meaning beyond
102/// distinguishing one writer from another, and the caller is responsible for
103/// ensuring two live writers never share one.
104#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
105pub struct ReplicaId(u64);
106
107impl ReplicaId {
108 pub const fn new(id: u64) -> Self {
109 Self(id)
110 }
111
112 pub const fn inner(&self) -> u64 {
113 self.0
114 }
115
116 pub fn encode_into(&self, buf: &mut Vec<u8>) {
117 varint_encode(self.0, buf)
118 }
119
120 pub fn encode(&self) -> Vec<u8> {
121 let mut buf = Vec::with_capacity(VARINT_MAX_LEN);
122 self.encode_into(&mut buf);
123 buf
124 }
125
126 pub fn decode(buf: &[u8])
127 -> Outcome<(Self, usize)>
128 {
129 let (n, len) = res!(varint_decode(buf));
130 Ok((Self(n), len))
131 }
132}
133
134impl fmt::Display for ReplicaId {
135 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
136 write!(f, "r{}", self.0)
137 }
138}
139
140
141/// Names a single operation: the replica that authored it, and that replica's
142/// own count at the time.
143///
144/// Counters start at one, so zero is available to mean "no operation yet".
145/// Ordering is by replica first and counter second, which gives a stable total
146/// order over identifiers; it is not a causal order, and nothing here claims it
147/// is.
148#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
149pub struct OpId {
150 pub replica: ReplicaId, // the replica that authored the operation
151 pub counter: u64, // that replica's own count, from one
152}
153
154impl OpId {
155 pub const fn new(replica: ReplicaId, counter: u64) -> Self {
156 Self { replica, counter }
157 }
158
159 /// Replica then counter, each a varint.
160 pub fn encode_into(&self, buf: &mut Vec<u8>) {
161 self.replica.encode_into(buf);
162 varint_encode(self.counter, buf);
163 }
164
165 pub fn encode(&self) -> Vec<u8> {
166 let mut buf = Vec::with_capacity(2 * VARINT_MAX_LEN);
167 self.encode_into(&mut buf);
168 buf
169 }
170
171 pub fn decode(buf: &[u8])
172 -> Outcome<(Self, usize)>
173 {
174 let (replica, n1) = res!(ReplicaId::decode(buf));
175 let (counter, n2) = res!(varint_decode(&buf[n1..]));
176 Ok((Self { replica, counter }, n1 + n2))
177 }
178
179 pub fn decode_all(buf: &[u8])
180 -> Outcome<Self>
181 {
182 let (id, len) = res!(Self::decode(buf));
183 if len != buf.len() {
184 return Err(err!(
185 "An OpId consumed {} of {} bytes, leaving {} trailing.",
186 len, buf.len(), buf.len() - len;
187 Decode, Input, Excessive));
188 }
189 Ok(id)
190 }
191
192 /// The shape is `[replica, counter]`.
193 pub fn to_dat(&self) -> Dat {
194 Dat::List(vec![
195 Dat::U64(self.replica.inner()),
196 Dat::U64(self.counter),
197 ])
198 }
199
200 pub fn from_dat(dat: &Dat)
201 -> Outcome<Self>
202 {
203 let pair = match dat {
204 Dat::List(v) if v.len() == 2 => v,
205 _ => return Err(err!(
206 "An OpId expects a 2-element Dat::List, got {:?}.", dat;
207 Decode, Input, Mismatch)),
208 };
209 let replica = match &pair[0] {
210 Dat::U64(n) => ReplicaId::new(*n),
211 other => return Err(err!(
212 "An OpId replica expects Dat::U64, got {:?}.", other;
213 Decode, Input, Mismatch)),
214 };
215 let counter = match &pair[1] {
216 Dat::U64(n) => *n,
217 other => return Err(err!(
218 "An OpId counter expects Dat::U64, got {:?}.", other;
219 Decode, Input, Mismatch)),
220 };
221 Ok(Self { replica, counter })
222 }
223}
224
225impl fmt::Display for OpId {
226 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
227 write!(f, "{}:{}", self.replica, self.counter)
228 }
229}
230
231impl std::str::FromStr for OpId {
232 type Err = Error<ErrTag>;
233
234 /// Reads back exactly what [`fmt::Display`] wrote: `r<replica>:<counter>`.
235 ///
236 /// It is here because an identifier is the one thing in this vocabulary a
237 /// person is ever asked to type. Every command and every page that lets
238 /// somebody name an operation -- reverting one, marking a flag reviewed,
239 /// settling a proposal -- has to turn that text back into an [`OpId`], and a
240 /// reader that each of them wrote for itself is a reader that accepts a
241 /// different set of spellings in each of them.
242 ///
243 /// ```
244 /// use oxedyne_fe2o3_ore::id::{OpId, ReplicaId};
245 ///
246 /// let id = OpId::new(ReplicaId::new(3065315576), 4);
247 /// assert_eq!(format!("{}", id), "r3065315576:4");
248 /// assert_eq!("r3065315576:4".parse::<OpId>().unwrap(), id);
249 /// ```
250 ///
251 /// The `r` is required, and so is the colon. Both are refused rather than
252 /// forgiven, because what a person typed is nearly always what a command
253 /// printed, and quietly accepting a second spelling would let one identifier
254 /// be written two ways in the very sidecars and messages that exist to be
255 /// compared with each other.
256 fn from_str(text: &str)
257 -> Outcome<Self>
258 {
259 let body = res!(text.strip_prefix('r').ok_or_else(|| err!(
260 "An operation identifier is written {:?}, and {:?} does not begin with \
261 {:?}.", "r<replica>:<counter>", text, "r";
262 Invalid, Input, Mismatch)));
263 let (replica, counter) = res!(body.split_once(':').ok_or_else(|| err!(
264 "An operation identifier is written {:?}, and {:?} holds no colon \
265 separating the replica from the counter.", "r<replica>:<counter>", text;
266 Invalid, Input, Missing)));
267 let replica = match replica.parse::<u64>() {
268 Ok(n) => n,
269 Err(e) => return Err(err!(e,
270 "The replica of the operation identifier {:?} is not a number.", text;
271 Invalid, Input, Mismatch)),
272 };
273 let counter = match counter.parse::<u64>() {
274 Ok(n) => n,
275 Err(e) => return Err(err!(e,
276 "The counter of the operation identifier {:?} is not a number.", text;
277 Invalid, Input, Mismatch)),
278 };
279 Ok(Self::new(ReplicaId::new(replica), counter))
280 }
281}
282
283
284/// Names one byte of content: the operation that created the run it belongs to,
285/// and the byte's offset within that run.
286///
287/// The name is computed, never minted: a splice inserting a thousand bytes
288/// brings a thousand content identifiers into existence at the cost of the one
289/// operation identifier it already has. A byte keeps its name for as long as the
290/// history does, wherever the byte is later placed.
291#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
292pub struct ContentId {
293 pub op: OpId, // the operation that created the byte
294 pub off: u64, // offset of the byte within that operation's inserted run
295}
296
297impl ContentId {
298 pub const fn new(op: OpId, off: u64) -> Self {
299 Self { op, off }
300 }
301
302 /// Names a file's **origin anchor**: byte zero of the one-byte atom that the
303 /// file's creation mints.
304 ///
305 /// The byte is born dead and never renders, so nothing a reader points at can
306 /// name it; what it is for is that an empty file is not empty in identifier
307 /// space, and a splice into one therefore binds after a byte like every other
308 /// splice does. `file` is the identity of the file, which is the identity of
309 /// the [`crate::op::Op::FileCreate`] that brought it into existence.
310 pub const fn origin(file: OpId) -> Self {
311 Self { op: file, off: 0 }
312 }
313
314 /// The shape is `[op, off]`.
315 pub fn to_dat(&self) -> Dat {
316 Dat::List(vec![
317 self.op.to_dat(),
318 Dat::U64(self.off),
319 ])
320 }
321
322 pub fn from_dat(dat: &Dat)
323 -> Outcome<Self>
324 {
325 let pair = match dat {
326 Dat::List(v) if v.len() == 2 => v,
327 _ => return Err(err!(
328 "A ContentId expects a 2-element Dat::List, got {:?}.", dat;
329 Decode, Input, Mismatch)),
330 };
331 let off = match &pair[1] {
332 Dat::U64(n) => *n,
333 other => return Err(err!(
334 "A ContentId offset expects Dat::U64, got {:?}.", other;
335 Decode, Input, Mismatch)),
336 };
337 Ok(Self {
338 op: res!(OpId::from_dat(&pair[0])),
339 off,
340 })
341 }
342}
343
344impl fmt::Display for ContentId {
345 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
346 write!(f, "{}+{}", self.op, self.off)
347 }
348}
349
350
351/// Names a half-open run `[from, to)` of content identifiers sharing one
352/// creating operation.
353///
354/// A run is the unit in which content is spoken about: what a splice removes,
355/// what a move takes with it. Naming a run costs one operation identifier and
356/// two offsets however long the run is, which is why the structure's bookkeeping
357/// tracks edits rather than bytes.
358///
359/// The bounds are private because [`ContentRange::new`] refuses a reversed
360/// range, and a public field would let a struct literal build one anyway. The
361/// arithmetic below subtracts the start from the end, so a reversed range is a
362/// panic in a debug build and a wraparound in a release one; the invariant has
363/// to hold for every range that exists, not only for those that came through
364/// the constructor.
365#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
366pub struct ContentRange {
367 op: OpId, // the operation that created the bytes
368 from: u64, // first offset, inclusive
369 to: u64, // last offset, exclusive
370}
371
372impl ContentRange {
373 /// An empty range is allowed, because splitting a run at its own edge is
374 /// arithmetic that should not have to be special-cased; a reversed one names
375 /// nothing and is a mistake.
376 pub fn new(op: OpId, from: u64, to: u64)
377 -> Outcome<Self>
378 {
379 if to < from {
380 return Err(err!(
381 "A ContentRange of {}+{}..{} is reversed; the end may not precede \
382 the start.", op, from, to;
383 Invalid, Input, Range));
384 }
385 Ok(Self { op, from, to })
386 }
387
388 pub const fn op(&self) -> OpId {
389 self.op
390 }
391
392 pub const fn from(&self) -> u64 {
393 self.from
394 }
395
396 pub const fn to(&self) -> u64 {
397 self.to
398 }
399
400 /// This is how a caller coalescing abutting runs grows one without rebuilding
401 /// it, and the only way the end moves from outside this module.
402 pub fn set_to(&mut self, to: u64)
403 -> Outcome<()>
404 {
405 if to < self.from {
406 return Err(err!(
407 "A ContentRange of {}+{}..{} would be reversed; the end may not \
408 precede the start.", self.op, self.from, to;
409 Invalid, Input, Range));
410 }
411 self.to = to;
412 Ok(())
413 }
414
415 pub const fn len(&self) -> u64 {
416 self.to - self.from
417 }
418
419 pub const fn is_empty(&self) -> bool {
420 self.to == self.from
421 }
422
423 pub const fn offsets(&self) -> Range<u64> {
424 self.from..self.to
425 }
426
427 pub fn contains(&self, cid: &ContentId) -> bool {
428 cid.op == self.op && cid.off >= self.from && cid.off < self.to
429 }
430
431 /// Ranges over different creating operations never intersect.
432 pub fn intersects(&self, other: &Self) -> bool {
433 self.op == other.op && self.from < other.to && other.from < self.to
434 }
435
436 pub fn intersection(&self, other: &Self)
437 -> Option<Self>
438 {
439 if !self.intersects(other) {
440 return None;
441 }
442 Some(Self {
443 op: self.op,
444 from: self.from.max(other.from),
445 to: self.to.min(other.to),
446 })
447 }
448
449 /// The shape is `[op, from, to]`.
450 pub fn to_dat(&self) -> Dat {
451 Dat::List(vec![
452 self.op.to_dat(),
453 Dat::U64(self.from),
454 Dat::U64(self.to),
455 ])
456 }
457
458 pub fn from_dat(dat: &Dat)
459 -> Outcome<Self>
460 {
461 let v = match dat {
462 Dat::List(v) if v.len() == 3 => v,
463 _ => return Err(err!(
464 "A ContentRange expects a 3-element Dat::List, got {:?}.", dat;
465 Decode, Input, Mismatch)),
466 };
467 let mut bound = [0u64; 2];
468 for (i, dat) in v[1..].iter().enumerate() {
469 bound[i] = match dat {
470 Dat::U64(n) => *n,
471 other => return Err(err!(
472 "A ContentRange bound expects Dat::U64, got {:?}.", other;
473 Decode, Input, Mismatch)),
474 };
475 }
476 Self::new(res!(OpId::from_dat(&v[0])), bound[0], bound[1])
477 }
478}
479
480impl fmt::Display for ContentRange {
481 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
482 write!(f, "{}+{}..{}", self.op, self.from, self.to)
483 }
484}
485
486
487/// Which side of a byte a gap lies on.
488#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
489pub enum Side {
490 Before,
491 After,
492}
493
494impl Side {
495 pub const fn code(&self) -> u8 {
496 match self {
497 Self::Before => 0,
498 Self::After => 1,
499 }
500 }
501
502 pub fn from_code(code: u8)
503 -> Outcome<Self>
504 {
505 match code {
506 0 => Ok(Self::Before),
507 1 => Ok(Self::After),
508 other => Err(err!(
509 "A Side code is 0 for Before or 1 for After, got {}.", other;
510 Decode, Input, Invalid)),
511 }
512 }
513}
514
515impl fmt::Display for Side {
516 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
517 match self {
518 Self::Before => write!(f, "before"),
519 Self::After => write!(f, "after"),
520 }
521 }
522}
523
524
525/// Names a gap in a file by the byte on one side of it.
526///
527/// An anchor is what an edit records instead of a position. Because it names
528/// content, a later move of that content carries the anchor with it, and an
529/// insertion written against it lands beside the same neighbour it was written
530/// beside rather than at the offset that neighbour happened to occupy.
531///
532/// An absent anchor -- `None` where one is expected -- means the start or the
533/// end of the file, which no byte names.
534#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
535pub struct Anchor {
536 pub content: ContentId, // the byte the gap is named by
537 pub side: Side, // which side of that byte the gap lies on
538}
539
540impl Anchor {
541 pub const fn new(content: ContentId, side: Side) -> Self {
542 Self { content, side }
543 }
544
545 /// The form a left origin takes.
546 pub const fn after(content: ContentId) -> Self {
547 Self { content, side: Side::After }
548 }
549
550 /// The form a right origin takes.
551 pub const fn before(content: ContentId) -> Self {
552 Self { content, side: Side::Before }
553 }
554
555 /// Constructs the anchor naming the start of a file: the gap after that
556 /// file's origin anchor.
557 ///
558 /// This is the left origin of a splice into an empty file, and it is an
559 /// ordinary anchor over an ordinary content identifier. Nothing new is spelled
560 /// on the wire for it; see [`ContentId::origin`].
561 pub const fn origin(file: OpId) -> Self {
562 Self::after(ContentId::origin(file))
563 }
564
565 /// The shape is `[content, side]`.
566 pub fn to_dat(&self) -> Dat {
567 Dat::List(vec![
568 self.content.to_dat(),
569 Dat::U8(self.side.code()),
570 ])
571 }
572
573 pub fn from_dat(dat: &Dat)
574 -> Outcome<Self>
575 {
576 let pair = match dat {
577 Dat::List(v) if v.len() == 2 => v,
578 _ => return Err(err!(
579 "An Anchor expects a 2-element Dat::List, got {:?}.", dat;
580 Decode, Input, Mismatch)),
581 };
582 let side = match &pair[1] {
583 Dat::U8(c) => res!(Side::from_code(*c)),
584 other => return Err(err!(
585 "An Anchor side expects Dat::U8, got {:?}.", other;
586 Decode, Input, Mismatch)),
587 };
588 Ok(Self {
589 content: res!(ContentId::from_dat(&pair[0])),
590 side,
591 })
592 }
593
594 /// Absence is the start or the end of the file.
595 pub fn opt_to_dat(anchor: &Option<Self>) -> Dat {
596 Dat::Opt(Box::new(anchor.as_ref().map(|a| a.to_dat())))
597 }
598
599 pub fn opt_from_dat(dat: &Dat)
600 -> Outcome<Option<Self>>
601 {
602 match dat {
603 Dat::Opt(boxed) => match boxed.as_ref() {
604 Some(inner) => Ok(Some(res!(Self::from_dat(inner)))),
605 None => Ok(None),
606 },
607 other => Err(err!(
608 "An optional Anchor expects Dat::Opt, got {:?}.", other;
609 Decode, Input, Mismatch)),
610 }
611 }
612}
613
614impl fmt::Display for Anchor {
615 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
616 write!(f, "{} {}", self.side, self.content)
617 }
618}
619
620
621#[cfg(test)]
622mod tests {
623 use super::*;
624
625 /// The values worth testing at the edges of the varint encoding: zero, one,
626 /// every seven bit group boundary either side, and the extremes of a `u64`.
627 fn boundary_values() -> Vec<u64> {
628 let mut v = vec![
629 0,
630 1,
631 127, // largest single byte value
632 128, // smallest two byte value
633 u64::MAX,
634 u64::MAX - 1,
635 u64::MAX / 2,
636 ];
637 for g in 1..10u32 {
638 let edge = 1u64 << (7 * g);
639 v.push(edge - 1);
640 v.push(edge);
641 v.push(edge + 1);
642 }
643 v
644 }
645
646 #[test]
647 fn varint_round_trip() -> Outcome<()> {
648 for n in boundary_values() {
649 let mut buf = Vec::new();
650 varint_encode(n, &mut buf);
651 assert!(buf.len() <= VARINT_MAX_LEN, "{} encoded to {} bytes", n, buf.len());
652 let (got, len) = res!(varint_decode(&buf));
653 assert_eq!(got, n);
654 assert_eq!(len, buf.len());
655 }
656 Ok(())
657 }
658
659 /// The encoding is a prefix code: a value decodes correctly with trailing
660 /// bytes present, consuming only its own.
661 #[test]
662 fn varint_decodes_as_a_prefix() -> Outcome<()> {
663 for n in boundary_values() {
664 let mut buf = Vec::new();
665 varint_encode(n, &mut buf);
666 let used = buf.len();
667 buf.extend_from_slice(b"trailing rubbish");
668 let (got, len) = res!(varint_decode(&buf));
669 assert_eq!(got, n);
670 assert_eq!(len, used);
671 }
672 Ok(())
673 }
674
675 /// Lengths grow one byte per seven bits, and no further.
676 #[test]
677 fn varint_lengths_are_as_expected() -> Outcome<()> {
678 let cases = [
679 (0u64, 1usize),
680 (127, 1),
681 (128, 2),
682 (16_383, 2),
683 (16_384, 3),
684 (u64::MAX, 10),
685 ];
686 for (n, want) in cases {
687 let mut buf = Vec::new();
688 varint_encode(n, &mut buf);
689 assert_eq!(buf.len(), want, "value {}", n);
690 }
691 Ok(())
692 }
693
694 #[test]
695 fn varint_rejects_truncation() -> Outcome<()> {
696 assert!(varint_decode(&[]).is_err());
697 assert!(varint_decode(&[0x80]).is_err());
698 assert!(varint_decode(&[0x80, 0x80, 0x80]).is_err());
699 Ok(())
700 }
701
702 /// An overlong encoding of a value is rejected, so each value has exactly
703 /// one spelling.
704 #[test]
705 fn varint_rejects_overlong_encodings() -> Outcome<()> {
706 assert!(varint_decode(&[0x80, 0x00]).is_err()); // overlong zero
707 assert!(varint_decode(&[0x81, 0x00]).is_err()); // overlong one
708 assert!(varint_decode(&[0xff, 0x80, 0x00]).is_err()); // overlong 127
709 Ok(())
710 }
711
712 #[test]
713 fn varint_rejects_overflow() -> Outcome<()> {
714 // Ten bytes whose final byte carries more than the one remaining bit.
715 let too_big = [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x02];
716 assert!(varint_decode(&too_big).is_err());
717 // Eleven bytes, every one continuing.
718 let too_long = [0x80; 11];
719 assert!(varint_decode(&too_long).is_err());
720 Ok(())
721 }
722
723 #[test]
724 fn varint_encodes_the_maximum() -> Outcome<()> {
725 let mut buf = Vec::new();
726 varint_encode(u64::MAX, &mut buf);
727 assert_eq!(buf.len(), VARINT_MAX_LEN);
728 assert_eq!(buf[VARINT_MAX_LEN - 1], 0x01);
729 let (got, _) = res!(varint_decode(&buf));
730 assert_eq!(got, u64::MAX);
731 Ok(())
732 }
733
734 #[test]
735 fn op_id_byte_round_trip() -> Outcome<()> {
736 for r in boundary_values() {
737 for c in boundary_values() {
738 let id = OpId::new(ReplicaId::new(r), c);
739 let buf = id.encode();
740 let back = res!(OpId::decode_all(&buf));
741 assert_eq!(id, back);
742 }
743 }
744 Ok(())
745 }
746
747 #[test]
748 fn op_id_decodes_as_a_prefix() -> Outcome<()> {
749 let id = OpId::new(ReplicaId::new(300), 70_000);
750 let mut buf = id.encode();
751 let used = buf.len();
752 buf.extend_from_slice(&[0xde, 0xad, 0xbe, 0xef]);
753 let (back, len) = res!(OpId::decode(&buf));
754 assert_eq!(back, id);
755 assert_eq!(len, used);
756 assert!(OpId::decode_all(&buf).is_err());
757 Ok(())
758 }
759
760 #[test]
761 fn op_id_dat_round_trip() -> Outcome<()> {
762 for r in boundary_values() {
763 for c in boundary_values() {
764 let id = OpId::new(ReplicaId::new(r), c);
765 let back = res!(OpId::from_dat(&id.to_dat()));
766 assert_eq!(id, back);
767 }
768 }
769 Ok(())
770 }
771
772 #[test]
773 fn op_id_from_dat_rejects_rubbish() -> Outcome<()> {
774 assert!(OpId::from_dat(&Dat::U64(7)).is_err());
775 assert!(OpId::from_dat(&Dat::List(vec![Dat::U64(1)])).is_err());
776 assert!(OpId::from_dat(&Dat::List(vec![
777 Dat::Str(fmt!("one")),
778 Dat::U64(2),
779 ])).is_err());
780 assert!(OpId::from_dat(&Dat::List(vec![
781 Dat::U64(1),
782 Dat::Str(fmt!("two")),
783 ])).is_err());
784 Ok(())
785 }
786
787 #[test]
788 fn op_id_orders_by_replica_then_counter() -> Outcome<()> {
789 let a = OpId::new(ReplicaId::new(1), 9);
790 let b = OpId::new(ReplicaId::new(2), 1);
791 let c = OpId::new(ReplicaId::new(1), 10);
792 assert!(a < b);
793 assert!(a < c);
794 assert!(c < b);
795 Ok(())
796 }
797
798 #[test]
799 fn op_id_displays_both_parts() -> Outcome<()> {
800 let id = OpId::new(ReplicaId::new(4), 17);
801 assert_eq!(fmt!("{}", id), "r4:17");
802 Ok(())
803 }
804
805 fn an_op() -> OpId {
806 OpId::new(ReplicaId::new(3), 9)
807 }
808
809 #[test]
810 fn content_id_dat_round_trip() -> Outcome<()> {
811 for off in boundary_values() {
812 let cid = ContentId::new(an_op(), off);
813 assert_eq!(cid, res!(ContentId::from_dat(&cid.to_dat())));
814 }
815 Ok(())
816 }
817
818 #[test]
819 fn content_range_dat_round_trip() -> Outcome<()> {
820 for (from, to) in [(0u64, 0u64), (0, 1), (7, 9), (0, u64::MAX)] {
821 let r = res!(ContentRange::new(an_op(), from, to));
822 assert_eq!(r, res!(ContentRange::from_dat(&r.to_dat())));
823 }
824 assert!(ContentRange::from_dat(&Dat::U64(1)).is_err());
825 assert!(ContentRange::from_dat(&Dat::List(vec![
826 an_op().to_dat(),
827 Dat::U64(5),
828 ])).is_err());
829 // A range whose end precedes its start is refused on the way back in.
830 assert!(ContentRange::from_dat(&Dat::List(vec![
831 an_op().to_dat(),
832 Dat::U64(9),
833 Dat::U64(2),
834 ])).is_err());
835 Ok(())
836 }
837
838 #[test]
839 fn content_range_refuses_only_reversal() -> Outcome<()> {
840 assert!(ContentRange::new(an_op(), 5, 4).is_err());
841 let empty = res!(ContentRange::new(an_op(), 5, 5));
842 assert!(empty.is_empty());
843 assert_eq!(empty.len(), 0);
844 Ok(())
845 }
846
847 /// The bounds read back as they went in, since nothing else can now see
848 /// them.
849 #[test]
850 fn content_range_reports_its_bounds() -> Outcome<()> {
851 let r = res!(ContentRange::new(an_op(), 4, 11));
852 assert_eq!(r.op(), an_op());
853 assert_eq!(r.from(), 4);
854 assert_eq!(r.to(), 11);
855 assert_eq!(r.len(), 7);
856 assert_eq!(r.offsets(), 4..11);
857 Ok(())
858 }
859
860 /// Moving the end keeps the invariant the constructor established: forward
861 /// or back to the start is allowed, past it is not, and a refusal leaves the
862 /// range as it was.
863 #[test]
864 fn content_range_end_may_not_pass_its_start() -> Outcome<()> {
865 let mut r = res!(ContentRange::new(an_op(), 4, 11));
866 res!(r.set_to(20));
867 assert_eq!(r.len(), 16);
868 res!(r.set_to(4));
869 assert!(r.is_empty());
870 assert!(r.set_to(3).is_err());
871 assert_eq!(r.to(), 4, "a refused move leaves the range alone");
872 Ok(())
873 }
874
875 /// Containment and intersection read the half-open bounds, and neither
876 /// crosses from one creating operation to another.
877 #[test]
878 fn content_range_arithmetic_is_half_open() -> Outcome<()> {
879 let op = an_op();
880 let other = OpId::new(ReplicaId::new(4), 1);
881 let r = res!(ContentRange::new(op, 10, 20));
882 assert!(!r.contains(&ContentId::new(op, 9)));
883 assert!(r.contains(&ContentId::new(op, 10)));
884 assert!(r.contains(&ContentId::new(op, 19)));
885 assert!(!r.contains(&ContentId::new(op, 20)), "the end is exclusive");
886 assert!(!r.contains(&ContentId::new(other, 15)),
887 "a byte of another atom is never in this range");
888 assert!(r.intersects(&res!(ContentRange::new(op, 15, 25))));
889 assert!(!r.intersects(&res!(ContentRange::new(op, 20, 30))),
890 "abutting ranges do not intersect");
891 assert!(!r.intersects(&res!(ContentRange::new(other, 10, 20))));
892 assert_eq!(
893 r.intersection(&res!(ContentRange::new(op, 15, 25))),
894 Some(res!(ContentRange::new(op, 15, 20))),
895 );
896 assert_eq!(r.intersection(&res!(ContentRange::new(op, 30, 40))), None);
897 Ok(())
898 }
899
900 #[test]
901 fn anchor_dat_round_trip() -> Outcome<()> {
902 let cid = ContentId::new(an_op(), 4);
903 for a in [Anchor::after(cid), Anchor::before(cid)] {
904 assert_eq!(a, res!(Anchor::from_dat(&a.to_dat())));
905 let opt = Some(a);
906 assert_eq!(opt, res!(Anchor::opt_from_dat(&Anchor::opt_to_dat(&opt))));
907 }
908 let none: Option<Anchor> = None;
909 assert_eq!(none, res!(Anchor::opt_from_dat(&Anchor::opt_to_dat(&none))));
910 assert!(Anchor::from_dat(&Dat::List(vec![
911 cid.to_dat(),
912 Dat::U8(7),
913 ])).is_err());
914 assert!(Anchor::opt_from_dat(&Dat::U8(0)).is_err());
915 Ok(())
916 }
917
918 /// A file's origin anchor is byte zero of the atom its creation mints, and
919 /// the anchor naming the start of that file binds after it.
920 #[test]
921 fn the_origin_anchor_is_an_ordinary_name() -> Outcome<()> {
922 let file = an_op();
923 assert_eq!(ContentId::origin(file), ContentId::new(file, 0));
924 assert_eq!(Anchor::origin(file), Anchor::after(ContentId::new(file, 0)));
925 // Nothing new is spelled: it round trips as any other anchor does.
926 let a = Anchor::origin(file);
927 assert_eq!(a, res!(Anchor::from_dat(&a.to_dat())));
928 Ok(())
929 }
930
931 #[test]
932 fn content_names_display_readably() -> Outcome<()> {
933 let cid = ContentId::new(an_op(), 4);
934 assert_eq!(fmt!("{}", cid), "r3:9+4");
935 assert_eq!(fmt!("{}", res!(ContentRange::new(an_op(), 4, 7))), "r3:9+4..7");
936 assert_eq!(fmt!("{}", Anchor::after(cid)), "after r3:9+4");
937 Ok(())
938 }
939
940 /// An operation identifier reads back exactly as it was written, and refuses
941 /// every spelling it was not.
942 ///
943 /// The round trip is the whole of the contract: what a person types is what
944 /// some command printed, so the reader is judged against the writer and not
945 /// against a grammar written out beside it. The values include the ones a
946 /// digest-minted replica actually produces, which are ten digits long, and the
947 /// extremes, where a lenient parser would silently wrap.
948 #[test]
949 fn an_operation_identifier_reads_back_as_it_was_written() -> Outcome<()> {
950 use std::str::FromStr;
951
952 for (replica, counter) in [
953 (1u64, 1u64),
954 (3_065_315_576, 4),
955 (2_215_465_083, 5),
956 (u64::MAX, u64::MAX),
957 (1, u64::MAX),
958 ] {
959 let id = OpId::new(ReplicaId::new(replica), counter);
960 let text = fmt!("{}", id);
961 assert_eq!(text, fmt!("r{}:{}", replica, counter));
962 assert_eq!(res!(OpId::from_str(&text)), id, "the text {:?}", text);
963 // And through the trait, which is how a caller reaches it.
964 let parsed: OpId = res!(text.parse());
965 assert_eq!(parsed, id);
966 }
967 // Everything the writer never wrote is refused rather than forgiven. A
968 // second accepted spelling of one identifier would let the same operation
969 // be written two ways in the very records that exist to be compared.
970 for bad in [
971 "",
972 "3:4", // the r is not decoration
973 "r3", // no counter
974 "r:4", // no replica
975 "r3:", // an empty counter
976 "R3:4", // the prefix is one character and it is lower case
977 " r3:4", // nothing is trimmed
978 "r3:4 ",
979 "r3:4:5", // a counter is a number, and 4:5 is not one
980 "r-3:4", // a replica is not negative
981 "r3:-4",
982 "r3.4", // the separator is a colon, which is what Display writes
983 "r18446744073709551616:1", // one past a u64, refused rather than wrapped
984 ] {
985 assert!(OpId::from_str(bad).is_err(), "the text {:?} was accepted", bad);
986 }
987 Ok(())
988 }
989}