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
131
132
133
134
135
136
137
138
139
140
141
142
143
144

extern crate alloc;

use alloc::vec::Vec;

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

use super::super::editor::{Replica, gossip_text};
use super::type_run;

#[test]
fn test_two_writers_interleave_words() {
    // Two replicas type separate chains at the origin. Each chain stays
    // contiguous, and the heads' ranks decide which word reads first.
    let roster = [1u32, 2u32];
    let mut a = Replica::new(1, &roster);
    let mut b = Replica::new(2, &roster);

    let _ = type_run(&mut a, "hello", None);
    let _ = type_run(&mut b, "world", None);

    gossip_text(&a, &mut b);
    gossip_text(&b, &mut a);

    assert_eq!(a.text(), "worldhello");
    assert_eq!(b.text(), a.text());
    assert_eq!(a.order(), b.order());
}

#[test]
fn test_typing_burst_with_laggard() {
    // A bottom purview row means the laggard has seen none of the burst, so one
    // owed delta must carry every written dot and no extra store dots.
    let roster = [1u32, 2u32];
    let mut writer = Replica::new(1, &roster);
    let laggard = Replica::new(2, &roster);

    let burst = 200usize;
    let mut anchor = None;
    for i in 0..burst {
        let ch = char::from(b'a' + u8::try_from(i % 26).unwrap_or(0));
        anchor = Some(writer.insert(ch, anchor));
    }
    assert_eq!(writer.visible_len(), burst);

    let delta = writer.text_owed(2).expect("station 2 is on the roster");
    let ship_count = delta.store().dots().count();
    assert_eq!(
        ship_count, burst,
        "the delta ships exactly what the laggard lacked"
    );

    let mut healed = laggard;
    let chars = writer.chars().clone();
    healed.absorb_text(1, &delta, &chars);
    assert_eq!(healed.text(), writer.text());
    assert_eq!(healed.order(), writer.order());
}

#[test]
fn test_concurrent_edit_and_delete_of_a_word() {
    // Delete supersedes only observed dots. The concurrent visual insert is a
    // fresh dot, so it survives and keeps the caret placement through tombstones.
    let roster = [1u32, 2u32];
    let mut deleter = Replica::new(1, &roster);
    let mut inserter = Replica::new(2, &roster);

    let dot_c = deleter.insert('c', None);
    let dot_a = deleter.insert('a', Some(dot_c));
    let dot_t = deleter.insert('t', Some(dot_a));
    assert_eq!(deleter.text(), "cat");

    gossip_text(&deleter, &mut inserter);
    assert_eq!(inserter.text(), "cat");

    deleter.delete(dot_c);
    deleter.delete(dot_a);
    deleter.delete(dot_t);
    assert_eq!(deleter.text(), "");

    let dot_x = inserter.insert_visual('X', Some(dot_a));
    assert_eq!(
        inserter.text(),
        "caXt",
        "the visual-insert rule places 'X' where the caret was: 'caXt', not the naive 'catX'"
    );

    gossip_text(&deleter, &mut inserter);
    gossip_text(&inserter, &mut deleter);

    assert_eq!(deleter.text(), "X");
    assert_eq!(inserter.text(), "X");
    assert_eq!(deleter.order(), inserter.order());
    assert!(deleter.order().contains(&dot_x));
    assert_eq!(deleter.skeleton_len(), 4);
    assert_eq!(deleter.visible_len(), 1);
}

/// Builds a run by repeated insert-before at the document start. Dots are
/// returned in reading order.
fn prepend_run(replica: &mut Replica, text: &str) -> Vec<Dot> {
    let mut run: Vec<Dot> = Vec::new();
    for ch in text.chars().rev() {
        let head = replica.order().first().copied();
        let dot = replica.insert_before_visual(ch, head);
        run.insert(0, dot);
    }
    run
}

#[test]
fn test_concurrent_backward_runs_stay_contiguous() {
    // The sided anchor cures concurrent prepends reading as interleaved runs.
    let roster = [1u32, 2u32];
    let mut a = Replica::new(1, &roster);
    let mut b = Replica::new(2, &roster);

    let run_a = prepend_run(&mut a, "ab");
    let run_b = prepend_run(&mut b, "xy");
    assert_eq!(a.text(), "ab");
    assert_eq!(b.text(), "xy");

    gossip_text(&a, &mut b);
    gossip_text(&b, &mut a);
    assert_eq!(a.order(), b.order(), "the two replicas converge");

    let order = a.order();
    let a_at = order.windows(run_a.len()).position(|w| w == run_a);
    let b_at = order.windows(run_b.len()).position(|w| w == run_b);
    assert!(
        a_at.is_some(),
        "run 'ab' interleaved (cured anomaly): {order:?}"
    );
    assert!(
        b_at.is_some(),
        "run 'xy' interleaved (cured anomaly): {order:?}"
    );
    assert_eq!(order.len(), 4);
    assert_eq!(
        a.text(),
        "xyab",
        "block-contiguous, not the interleaved 'xayb'"
    );
    assert_eq!(b.text(), a.text());
}