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

//! The kind question: the probe's second charge. A kind *tag* is expressible
//! today (a field register; concurrent writes surface as siblings), but
//! kind-shaped *content* is not: `DotMap<K, S>` fixes one `S` per map, so the
//! recipe runs parallel per-kind maps (a paragraph map AND a table map),
//! the Kleppmann-Beresford per-kind-slots semantics arrived at with zero new
//! surface. These scripts record exactly where that recipe hurts, which is
//! stage B's decision evidence: no canonical drop of a superseded kind's
//! subtree, nothing preventing a cross-kind read, and a key space that never
//! shrinks.

extern crate alloc;

use alloc::vec::Vec;

use super::page::Page;
use super::render::Rendered;
use super::{PARAGRAPH, TABLE, gossip_fields, gossip_page, gossip_para, gossip_table};

#[test]
fn test_concurrent_kinds_surface_as_siblings_in_both_maps() {
    // Two replicas concurrently decide what one block is. The kind register
    // keeps both writes as siblings (the machine never chooses), and each
    // side's content lands in its own kind map, so after convergence the
    // block is *honestly plural*: MultiKind on the surface, state in both
    // maps underneath, resolution the caller's.
    let mut a = Page::new(1);
    let mut b = Page::new(2);

    let block = a.create_block(PARAGRAPH, "draft", None);
    gossip_page(&a, &mut b);
    assert_eq!(b.kinds(block), [PARAGRAPH]);

    // Genuinely concurrent kind writes: each replica re-types the block
    // without seeing the other's write. Both supersede the *original* kind
    // dot (both observed it), neither supersedes the other, so both survive.
    // (A first draft of this script had only `b` write a kind after full
    // gossip, and the observed remove correctly resolved it: a causally
    // *later* kind write is not a conflict. Concurrency is what makes one.)
    a.set_kind(block, PARAGRAPH);
    let _ = a.type_into(block, 'h', None);
    b.set_kind(block, TABLE);
    b.set_cell(block, 1, "x1");

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

    let kinds: Vec<&str> = a.kinds(block);
    assert_eq!(
        kinds,
        [PARAGRAPH, TABLE],
        "concurrent kind writes are siblings, ascending by dot"
    );
    assert_eq!(
        a.render(),
        [Rendered::MultiKind { block, kinds }],
        "the conflict renders surfaced, never resolved"
    );
    assert_eq!(a.render(), b.render());
    assert!(
        a.para_present(block) && a.table_present(block),
        "both kind maps hold the block: the read must consult every map, \
         the key-space duplication cost on the record"
    );
}

#[test]
fn test_kind_reassignment_leaves_the_stale_subtree_readable() {
    // One writer honestly reassigns a paragraph block to a table: supersede
    // the kind register, write table content, retract the paragraph chars.
    // Three deltas on three pairs, and nothing orders their delivery. The
    // window where a peer holds the new kind but not the paragraph retract
    // is the recorded hazard: the conjunction render stays honest (it is
    // kind-driven), but the stale subtree is still readable through the
    // paragraph map, and no type refuses that read.
    let mut writer = Page::new(1);
    let mut peer = Page::new(2);

    let block = writer.create_block(PARAGRAPH, "draft", None);
    let first = writer.type_into(block, 'h', None);
    let _ = writer.type_into(block, 'i', Some(first));
    gossip_page(&writer, &mut peer);
    assert_eq!(peer.para_text(block), "hi");

    // The reassignment: kind register superseded, cells written, chars
    // retracted (the honest cross-pair cleanup a careful caller runs).
    writer.set_kind(block, TABLE);
    writer.set_cell(block, 1, "x1");
    writer.retract_para_content(block);

    // Deliver everything EXCEPT the paragraph retract.
    gossip_fields(&writer, &mut peer);
    gossip_table(&writer, &mut peer);

    assert_eq!(
        peer.render(),
        [Rendered::Table { block, rows: 1 }],
        "the kind-driven conjunction render never shows the stale paragraph"
    );
    assert_eq!(
        peer.para_text(block),
        "hi",
        "but the superseded kind's subtree is still held and readable: \
         no canonical drop exists across pairs, the stage-B exhibit"
    );

    // The retract arrives: the chars die, yet the key survives on the
    // sequence's tombstoned skeleton (grow-only by charter), so the key
    // space never shrinks; reclamation is the watermark family's face.
    gossip_para(&writer, &mut peer);
    assert_eq!(peer.para_text(block), "");
    assert_eq!(peer.para_visible_len(block), 0);
    assert!(
        peer.para_present(block),
        "the tombstoned sequence keeps the key alive after the retract"
    );
    assert_eq!(peer.para_skeleton_len(block), 2);
}