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

extern crate alloc;

use alloc::vec::Vec;

use crate::metis::{Anchor, Dot, Dotted};

use super::super::{Seq, clock, delete, insert, weave_at};

#[test]
fn test_children_of_agrees_with_the_order_sibling_bucket() {
    // `children_of(anchor)` yields the anchor's skeleton children in the
    // `order()` sibling order (rank descending, dot ascending on ties), visible
    // and tombstone alike. Two concurrent siblings at the origin, plus a chain.
    let mut a: Seq = Dotted::new();
    let mut b: Seq = Dotted::new();
    let ca = clock(1);
    let cb = clock(2);
    let da = insert(&mut a, &ca, 1, None);
    let db = insert(&mut b, &cb, 2, None);
    let merged = a.merge(&b);
    // A child hangs off whichever origin-sibling reads first.
    let head = merged.store().order()[0];
    let mut merged = merged;
    let cc = clock(1);
    let dc = insert(&mut merged, &cc, 1, Some(head));

    // The origin bucket equals the two origin-siblings in sibling order.
    let origin_children: Vec<Dot> = merged.store().children_of(Anchor::Origin).collect();
    let expected_origin = if da == head { [da, db] } else { [db, da] };
    assert_eq!(origin_children, expected_origin);
    // `head`'s After bucket is exactly its one child.
    let head_children: Vec<Dot> = merged
        .store()
        .children_of(Anchor::After(head.into()))
        .collect();
    assert_eq!(head_children, [dc]);
    // A dead-end tombstone (delete `dc`) still appears under its anchor: the
    // index mirrors the skeleton, not visibility.
    delete(&mut merged, dc);
    let head_children_after: Vec<Dot> = merged
        .store()
        .children_of(Anchor::After(head.into()))
        .collect();
    assert_eq!(head_children_after, [dc]);
}

#[test]
fn test_children_of_head_is_the_rank_to_beat_on_both_sides() {
    // The head of `children_of(anchor)` is the highest-ranked incumbent that a
    // fresh sibling must outrank to land adjacent to the anchor, and this holds
    // uniformly for an After bucket and a Before bucket (S127). Build two After
    // siblings and two Before siblings of one origin element, each pair with a
    // known rank order, and assert the stored head is the max-rank one both ways.
    let clk = clock(1);
    let mut r: Seq = Dotted::new();
    let base = insert(&mut r, &clk, 1, None);

    // Two After-children of `base`: low rank first, then high rank.
    let after_lo = weave_at(&mut r, &clk, 1, Anchor::After(base.into()));
    let after_hi = weave_at(&mut r, &clk, 1, Anchor::After(base.into()));
    // Two Before-children of `base`: low rank first, then high rank.
    let before_lo = weave_at(&mut r, &clk, 1, Anchor::Before(base.into()));
    let before_hi = weave_at(&mut r, &clk, 1, Anchor::Before(base.into()));

    // Stored order is rank DESCENDING on both sides, so the high-rank sibling is
    // the head of each bucket (the rank a newcomer must beat).
    let after: Vec<Dot> = r.store().children_of(Anchor::After(base.into())).collect();
    let before: Vec<Dot> = r.store().children_of(Anchor::Before(base.into())).collect();
    assert_eq!(after, [after_hi, after_lo]);
    assert_eq!(before, [before_hi, before_lo]);

    // And the stored head reads adjacent to the anchor in `order()`: the After
    // head right after `base`, the Before head right before it.
    let order = r.store().order();
    let base_at = order.iter().position(|&d| d == base).unwrap();
    assert_eq!(order[base_at + 1], after_hi, "After head reads right after");
    assert_eq!(
        order[base_at - 1],
        before_hi,
        "Before head reads right before"
    );
}