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

use super::super::super::support::dot;
use super::dots;
use crate::metis::{DotCollision, DotMap, DotSet};

#[test]
fn test_insert_refuses_the_same_dot_under_two_keys() {
    // Support exactness: a dot names one write, so it cannot straddle two
    // keys. The second insert shares dot (1, 1) with key 7, so it is refused
    // and the map is left exactly as it was.
    let mut map: DotMap<u8, DotSet> = DotMap::new();
    assert!(map.insert(7, dots(&[(1, 1), (1, 2)])));
    let before = map.clone();
    assert!(!map.insert(9, dots(&[(1, 1)])));
    assert_eq!(map, before);
    assert!(map.get(&9).is_none());
}

#[test]
fn test_insert_replaces_the_same_key_with_overlapping_dots() {
    // Replacing the same key is allowed even when the new store overlaps the
    // old one it displaces: the old store leaves with the key, so support
    // exactness is preserved.
    let mut map: DotMap<u8, DotSet> = DotMap::new();
    assert!(map.insert(7, dots(&[(1, 1)])));
    assert!(map.insert(7, dots(&[(1, 1), (1, 2)])));
    let held = map.get(&7).expect("the key is still held");
    assert!(held.contains(dot(1, 1)) && held.contains(dot(1, 2)));
    assert_eq!(map.len(), 1);
}

#[test]
fn test_insert_accepts_a_disjoint_second_key() {
    // A second key whose dots are disjoint from every other key is accepted.
    let mut map: DotMap<u8, DotSet> = DotMap::new();
    assert!(map.insert(7, dots(&[(1, 1)])));
    assert!(map.insert(9, dots(&[(1, 2), (2, 1)])));
    assert_eq!(map.len(), 2);
    assert!(map.get(&7).is_some_and(|held| held.contains(dot(1, 1))));
    assert!(map.get(&9).is_some_and(|held| held.contains(dot(1, 2))));
}

#[test]
fn test_from_disjoint_matches_repeated_insert() {
    // The one-pass build agrees with the documented quadratic build: the same
    // disjoint entries yield the same map whichever way it is assembled.
    let entries = [
        (7u8, dots(&[(1, 1), (1, 2)])),
        (9u8, dots(&[(2, 1), (3, 5)])),
        (4u8, dots(&[(1, 3)])),
    ];
    let mut by_insert: DotMap<u8, DotSet> = DotMap::new();
    for (key, store) in entries.clone() {
        assert!(by_insert.insert(key, store));
    }
    let by_batch = DotMap::from_disjoint(entries).expect("the entries are disjoint");
    assert_eq!(by_batch, by_insert);
    assert_eq!(by_batch.len(), 3);
}

#[test]
fn test_from_disjoint_drops_bottom_stores_like_singleton() {
    // A bottom store contributes no key (canonical form), exactly as repeated
    // insertion and singleton drop it.
    let built = DotMap::from_disjoint([
        (7u8, dots(&[(1, 1)])),
        (9u8, DotSet::new()), // bottom: dropped
    ])
    .expect("the non-bottom entry is disjoint");
    assert_eq!(built.len(), 1);
    assert!(built.get(&9).is_none());
}

#[test]
fn test_from_disjoint_refuses_with_the_colliding_dot_witness() {
    // Two different keys claiming dot (1, 1) is refused, and the witness names
    // exactly that dot; nothing is built.
    let built = DotMap::from_disjoint([
        (7u8, dots(&[(1, 1), (1, 2)])),
        (9u8, dots(&[(1, 1)])), // collides on (1, 1)
    ]);
    assert_eq!(built.err(), Some(DotCollision { dot: dot(1, 1) }));
}

#[test]
fn test_from_disjoint_last_write_wins_for_a_repeated_key() {
    // A repeated key replaces its earlier store (as insert does), and the
    // replacement may overlap the store it displaces without a false collision,
    // because the old dots leave with the key.
    let built = DotMap::from_disjoint([
        (7u8, dots(&[(1, 1)])),
        (7u8, dots(&[(1, 1), (1, 2)])), // same key: replaces, overlap is fine
    ])
    .expect("a repeated key replaces rather than collides");
    assert_eq!(built.len(), 1);
    let held = built.get(&7).expect("the key survives");
    assert!(held.contains(dot(1, 1)) && held.contains(dot(1, 2)));
}