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

use crate::metis::Dotted;

use super::super::{Seq, clock, delete, insert};
use super::{claim, condense};

#[test]
fn test_condense_monotone_claim_is_idempotent() {
    let build = || {
        let mut r: Seq = Dotted::new();
        let clk = clock(1);
        let d0 = insert(&mut r, &clk, 1, None);
        let d1 = insert(&mut r, &clk, 1, Some(d0));
        let d2 = insert(&mut r, &clk, 1, Some(d1));
        let d3 = insert(&mut r, &clk, 1, Some(d2));
        delete(&mut r, d1);
        delete(&mut r, d2);
        delete(&mut r, d3);
        (r, d1, d2, d3)
    };

    let (mut staged, d1, d2, d3) = build();
    let s1 = condense(&mut staged, &claim(&[d2, d3]));
    assert_eq!(s1, 2);
    let s2 = condense(&mut staged, &claim(&[d1, d2, d3]));
    assert_eq!(s2, 1);

    let (mut one_shot, _, _, _) = build();
    let o = condense(&mut one_shot, &claim(&[d1, d2, d3]));
    assert_eq!(o, 3);

    assert_eq!(
        staged.store().skeleton_len(),
        one_shot.store().skeleton_len()
    );
    assert_eq!(staged.store().order(), one_shot.store().order());
    for &dot in &[d1, d2, d3] {
        assert!(staged.store().locus(dot).is_none());
        assert!(one_shot.store().locus(dot).is_none());
    }
}

#[test]
fn test_condense_visible_guard_leaves_a_named_visible_dot_untouched() {
    let mut r: Seq = Dotted::new();
    let clk = clock(1);
    let d0 = insert(&mut r, &clk, 1, None);
    let d1 = insert(&mut r, &clk, 1, Some(d0));

    let excised = condense(&mut r, &claim(&[d0, d1]));
    assert_eq!(excised, 0);
    assert!(r.store().locus(d0).is_some());
    assert!(r.store().locus(d1).is_some());
    assert_eq!(r.store().order(), [d0, d1]);
}

#[test]
fn test_condense_gossip_cycle_relearns_then_reexcises() {
    let mut a: Seq = Dotted::new();
    let clk = clock(1);
    let d0 = insert(&mut a, &clk, 1, None);
    let d1 = insert(&mut a, &clk, 1, Some(d0));
    delete(&mut a, d1);
    let order = a.store().order();

    let peer = a.clone();
    let retired = claim(&[d1]);

    let first = condense(&mut a, &retired);
    assert_eq!(first, 1);
    assert!(a.store().locus(d1).is_none());
    assert_eq!(a.store().order(), order);

    a = a.merge(&peer);
    assert!(a.store().locus(d1).is_some());
    assert!(!a.store().is_visible(d1));
    assert_eq!(a.store().order(), order);

    let second = condense(&mut a, &retired);
    assert_eq!(second, first);
    assert!(a.store().locus(d1).is_none());
    assert_eq!(a.store().order(), order);
}

#[test]
fn test_condense_is_idempotent_with_the_same_claim() {
    let mut r: Seq = Dotted::new();
    let clk = clock(1);
    let d0 = insert(&mut r, &clk, 1, None);
    let d1 = insert(&mut r, &clk, 1, Some(d0));
    let d2 = insert(&mut r, &clk, 1, Some(d1));
    delete(&mut r, d1);
    delete(&mut r, d2);
    let retired = claim(&[d1, d2]);

    let first = condense(&mut r, &retired);
    assert_eq!(first, 2);
    let second = condense(&mut r, &retired);
    assert_eq!(second, 0);
    assert_eq!(r.store().order(), [d0]);
}