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

extern crate alloc;

use alloc::vec::Vec;

use super::super::super::support::dot;
use super::{Doc, add, dots, remove_observed};
use crate::metis::{DotMap, DotSet, DotStore, Dotted};

#[test]
fn test_write_flow_lands_the_dot() {
    let mut doc = Doc::new();
    let (_, fresh) = add(&mut doc, 1, 7);
    assert_eq!(fresh, dot(1, 1));
    assert!(
        doc.store()
            .get(&7)
            .is_some_and(|held| held.contains(dot(1, 1)))
    );
    assert!(doc.context().contains(dot(1, 1)));
    // The next assignment is fresh because the delta was merged.
    assert_eq!(doc.next_dot(1), dot(1, 2));
}

#[test]
fn test_removal_does_not_resurrect_through_a_stale_peer() {
    // A writes, B learns it, A removes. The stale copy at B must not bring
    // the value back: B's dot is covered by A's context with no survivor, so
    // the merge honors the removal. A plain union of stores would resurrect.
    let mut a = Doc::new();
    let _ = add(&mut a, 1, 7);
    let mut b = Doc::new();
    b = b.merge(&a); // B holds the stale copy.
    let _ = remove_observed(&mut a, 7);
    assert!(a.store().get(&7).is_none());
    let rejoined = a.merge(&b);
    assert!(rejoined.store().get(&7).is_none());
    assert_eq!(rejoined, b.merge(&a)); // and symmetrically
    // A replica that never saw the dot at all learns the removal the same
    // way: nothing to resurrect, context remembers.
    let fresh = Doc::new().merge(&a);
    assert!(fresh.store().get(&7).is_none());
    assert!(fresh.context().contains(dot(1, 1)));
}

#[test]
fn test_concurrent_add_survives_concurrent_removal() {
    // The add-wins shape a collaborative editor needs: B removes the key
    // having observed only dot (1, 1); A concurrently writes dot (1, 2)
    // under the same key. The removal supersedes exactly what it observed,
    // so the unseen concurrent write survives the merge.
    let mut a = Doc::new();
    let _ = add(&mut a, 1, 7);
    let mut b = Doc::new();
    b = b.merge(&a);
    let _ = remove_observed(&mut b, 7); // supersedes (1, 1) only
    let _ = add(&mut a, 1, 7); // concurrent: (1, 2), unseen at B
    let merged = a.merge(&b);
    let held = merged.store().get(&7).expect("the concurrent add survives");
    assert!(!held.contains(dot(1, 1)));
    assert!(held.contains(dot(1, 2)));
}

#[test]
fn test_next_dot_survives_removal() {
    // The doomed-dot trap, pinned: after a removal the store forgets the
    // dot, but assignment reads the context, which does not. A store-based
    // assignment would re-issue (1, 1), and every peer whose context covers
    // it would drop the new write as already-seen.
    let mut doc = Doc::new();
    let _ = add(&mut doc, 1, 7);
    let _ = remove_observed(&mut doc, 7);
    assert!(doc.store().is_bottom()); // the store has forgotten
    assert_eq!(doc.next_dot(1), dot(1, 2)); // the context has not
}

#[test]
fn test_key_vanishes_when_every_dot_is_superseded() {
    // Canonical form on the composed shape: a key with no surviving dot is
    // absent, not empty, so "key present" and "some dot survives" are the
    // same fact and equality stays structural.
    let mut doc = Doc::new();
    let _ = add(&mut doc, 1, 7);
    let _ = add(&mut doc, 1, 9);
    let _ = remove_observed(&mut doc, 7);
    assert!(doc.store().get(&7).is_none());
    assert_eq!(doc.store().len(), 1);
    let keys: Vec<u8> = doc.store().iter().map(|(&key, _)| key).collect();
    assert_eq!(keys, [9]);
}

#[test]
fn test_nested_composition_removes_at_the_leaf() {
    // The axis composes: a map of maps of dots, one context vouching for
    // every level. Removing the inner key's observed dots empties it, the
    // canonical drop cascades, and the outer key survives only where an
    // inner dot does.
    type Nested = Dotted<DotMap<u8, DotMap<u8, DotSet>>>;
    let mut doc = Nested::new();
    let fresh = doc.next_dot(1);
    let inner = DotMap::singleton(2u8, dots(&[(fresh.station(), fresh.counter())]));
    let delta = Dotted::from_store(DotMap::singleton(1u8, inner));
    doc = doc.merge(&delta);
    assert!(
        doc.store()
            .get(&1)
            .and_then(|inner| inner.get(&2))
            .is_some_and(|held| held.contains(dot(1, 1)))
    );
    // Supersede the one dot: inner key, then outer key, both vanish.
    let removal = Dotted::from_context(dots(&[(1, 1)]));
    doc = doc.merge(&removal);
    assert!(doc.store().is_bottom());
    assert_eq!(doc.next_dot(1), dot(1, 2));
}