minerva 0.2.0

Causal ordering for distributed systems
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

extern crate alloc;

use alloc::string::String;
use alloc::vec::Vec;

use crate::metis::{Dot, DotSet, DotStore, Dotted};

use super::Inscribed;

/// The multi-value register a collaborative editor reads over the foreign
/// store: caller keys are dots, values are writes, and concurrent writes are
/// siblings.
type Register = Dotted<Inscribed>;

/// A one-dot `DotSet`, for building removal contexts declaratively.
fn context_of(dots: &[Dot]) -> DotSet {
    let mut set = DotSet::new();
    for &dot in dots {
        assert!(set.insert(dot));
    }
    set
}

/// Writes a fresh value and supersedes every currently visible register dot.
fn write(reg: &mut Register, station: u32, value: &str) -> (Register, Dot) {
    let fresh = reg.next_dot(station);
    let mut context = context_of(&[fresh]);
    let observed: Vec<Dot> = reg.store().dots().collect();
    for &obs in &observed {
        let _ = context.insert(obs);
    }
    let store = Inscribed::singleton(fresh, String::from(value));
    let delta = Dotted::try_new(store, context).expect("the fresh pair is covered by construction");
    *reg = reg.merge(&delta);
    (delta, fresh)
}

/// Clears exactly the dots the register currently carries.
fn clear_observed(reg: &mut Register) -> Register {
    let mut context = DotSet::new();
    for observed in reg.store().dots() {
        let _ = context.insert(observed);
    }
    let delta = Dotted::from_context(context);
    *reg = reg.merge(&delta);
    delta
}

#[test]
fn test_register_write_supersedes_observed() {
    let mut reg = Register::new();
    let (_, d_a) = write(&mut reg, 1, "a");
    assert_eq!(reg.store().value(d_a), Some(&String::from("a")));

    let (_, d_b) = write(&mut reg, 1, "b");
    assert!(!reg.store().holds(d_a));
    assert_eq!(reg.store().value(d_b), Some(&String::from("b")));
    let live: Vec<Dot> = reg.store().dots().collect();
    assert_eq!(live, [d_b]);
    assert!(reg.context().contains(d_a));
}

#[test]
fn test_register_concurrent_writes_are_siblings() {
    let mut a = Register::new();
    let mut b = Register::new();
    let (_, d_a) = write(&mut a, 1, "alpha");
    let (_, d_b) = write(&mut b, 2, "beta");

    let merged = a.merge(&b);
    assert_eq!(merged.store().value(d_a), Some(&String::from("alpha")));
    assert_eq!(merged.store().value(d_b), Some(&String::from("beta")));
    let mut siblings: Vec<Dot> = merged.store().dots().collect();
    siblings.sort_unstable();
    assert_eq!(siblings, [d_a, d_b]);

    let mut joined = merged;
    let (_, d_c) = write(&mut joined, 1, "gamma");
    assert!(!joined.store().holds(d_a));
    assert!(!joined.store().holds(d_b));
    let live: Vec<Dot> = joined.store().dots().collect();
    assert_eq!(live, [d_c]);
    assert_eq!(joined.store().value(d_c), Some(&String::from("gamma")));
}

#[test]
fn test_register_observed_clear_empties_without_resurrect() {
    let mut a = Register::new();
    let (_, d) = write(&mut a, 1, "held");

    let mut b = Register::new();
    b = b.merge(&a);
    assert_eq!(b.store().value(d), Some(&String::from("held")));

    let _ = clear_observed(&mut a);
    assert!(a.store().is_bottom());

    let rejoined = a.merge(&b);
    assert!(rejoined.store().is_bottom());
    assert_eq!(rejoined, b.merge(&a));

    let fresh = Register::new().merge(&a);
    assert!(fresh.store().is_bottom());
    assert!(fresh.context().contains(d));
}

#[test]
fn test_register_folds_converge_in_both_orders() {
    let mut r0 = Register::new();
    let mut r1 = Register::new();
    let mut r2 = Register::new();

    let _ = write(&mut r0, 0, "zero");
    let _ = write(&mut r1, 1, "one");
    r1 = r1.merge(&r0);
    let _ = write(&mut r2, 2, "two");
    let _ = clear_observed(&mut r1);

    let replicas = [r0, r1, r2];
    let forward = replicas.iter().fold(Register::new(), |acc, r| acc.merge(r));
    let backward = replicas
        .iter()
        .rev()
        .fold(Register::new(), |acc, r| acc.merge(r));
    assert_eq!(forward, backward);

    for r in &replicas {
        assert_eq!(&forward.merge(r), &forward);
    }
}