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

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

/// A map of caller keys to registers: `Dotted<DotMap<u8, DotFun<&str>>>`, one
/// register per key (an editor's per-element metadata, say).
type RegisterMap = Dotted<DotMap<u8, DotFun<&'static str>>>;

/// Writes `value` under `key` in the map, superseding the key's currently
/// observed dots. Returns the fresh dot.
fn map_write(map: &mut RegisterMap, station: u32, key: u8, value: &'static str) -> Dot {
    let dot = map.next_dot(station);
    let mut context = DotSet::new();
    let _ = context.insert(dot);
    if let Some(reg) = map.store().get(&key) {
        for observed in reg.dots() {
            let _ = context.insert(observed);
        }
    }
    let store = DotMap::singleton(key, DotFun::singleton(dot, value));
    let delta = Dotted::try_new(store, context).expect("the fresh pair is covered");
    *map = map.merge(&delta);
    dot
}

/// Clears the key's observed dots in the map (a pure-context delta).
fn map_clear(map: &mut RegisterMap, key: u8) {
    let mut context = DotSet::new();
    if let Some(reg) = map.store().get(&key) {
        for observed in reg.dots() {
            let _ = context.insert(observed);
        }
    }
    let delta = Dotted::from_context(context);
    *map = map.merge(&delta);
}

#[test]
fn test_keyed_register_map_writes_and_clears_per_key() {
    // Per-key writes and observed clears behave, and a key vanishes when its
    // last dot is superseded (canonical form at the composed level).
    let mut map = RegisterMap::new();
    let d_t = map_write(&mut map, 1, 10, "title");
    let d_a = map_write(&mut map, 1, 20, "author");

    assert_eq!(
        map.store().get(&10).and_then(|r| r.get(d_t)),
        Some(&"title")
    );
    assert_eq!(
        map.store().get(&20).and_then(|r| r.get(d_a)),
        Some(&"author")
    );
    assert_eq!(map.store().len(), 2);

    // A superseding write under key 10 replaces its value; key stays present.
    let d_t2 = map_write(&mut map, 1, 10, "TITLE");
    assert_eq!(map.store().get(&10).and_then(|r| r.get(d_t)), None);
    assert_eq!(
        map.store().get(&10).and_then(|r| r.get(d_t2)),
        Some(&"TITLE")
    );

    // Clearing key 20's observed dot removes the key entirely: its last dot is
    // superseded, so the canonical map drops it.
    map_clear(&mut map, 20);
    assert!(map.store().get(&20).is_none());
    assert_eq!(map.store().len(), 1);
    // The context still remembers the cleared dot (no resurrection).
    assert!(map.context().contains(d_a));
}

#[test]
fn test_keyed_register_map_key_vanishes_when_last_dot_superseded() {
    // Two replicas write concurrently under the same key from an empty
    // ancestor, then one clears both observed dots after learning them: the
    // key vanishes only when every surviving dot is superseded.
    let mut a = RegisterMap::new();
    let mut b = RegisterMap::new();
    let _ = map_write(&mut a, 1, 5, "x");
    let _ = map_write(&mut b, 2, 5, "y");

    let mut joined = a.merge(&b);
    // Both siblings live under key 5.
    let reg = joined.store().get(&5).expect("key 5 present");
    assert_eq!(reg.len(), 2);

    // Clearing the key's observed (both) dots empties it, and the key vanishes.
    map_clear(&mut joined, 5);
    assert!(joined.store().get(&5).is_none());
    assert!(joined.store().is_empty());
}