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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

//! The kind reads: surfaced plurality, the checked projection, and the
//! emptiness verdict stage A could not express (a delivered empty block
//! classified as undelivered forever; here, tag present with bottom content
//! *means* empty).

extern crate alloc;

use alloc::vec::Vec;

use super::super::super::support::dot;
use crate::metis::{Anchor, DotSet, DotStore, Dotted, Kind, KindPlurality, Locus, NodeContent};

use super::super::{Author, TestNode, rank};
use super::{page_with, seq_block, sync, tag_block};

#[test]
fn test_kinds_present_reads_tag_claims_and_shaped_content() {
    // A tag claim alone is evidence; shaped content alone is evidence; the
    // two agree in the honest steady state and union when they differ.
    let mut node = tag_block(dot(1, 1), Kind::Sequence);
    let kinds = node.kinds_present();
    assert_eq!(kinds.len(), 1);
    assert!(kinds.contains(Kind::Sequence));

    assert!(node.weave(
        dot(1, 2),
        Locus {
            anchor: Anchor::Origin,
            rank: rank(1),
        }
    ));
    assert_eq!(node.kinds_present().len(), 1, "tag and shape agree");

    assert!(node.write_register(dot(1, 3), "stray"));
    let kinds = node.kinds_present();
    assert_eq!(kinds.len(), 2, "untagged shaped content is still evidence");
    assert!(kinds.contains(Kind::Register) && kinds.contains(Kind::Sequence));
    assert_eq!(
        kinds.iter().collect::<Vec<_>>(),
        [Kind::Register, Kind::Sequence],
        "iteration is the fixed kind order"
    );
}

#[test]
fn test_a_tag_only_node_is_an_empty_node_of_its_kind() {
    // The stage A limit, cured structurally: canonical form dropped a bottom
    // content store, so absence could not say "empty" and a fully delivered
    // empty block classified as undelivered forever. Here the tag and the
    // content ride one pair: a tag-only node is not bottom, keeps its key in
    // the parent map, and reads as the empty content of its kind.
    let mut page: Dotted<TestNode> = Dotted::new();
    page.merge_from(&Dotted::from_store(page_with(
        7,
        tag_block(dot(1, 1), Kind::Sequence),
    )));

    let block = page.store().children().get(&7).expect("the key is alive");
    assert!(
        !block.is_bottom(),
        "a tagged empty node is state, not absence"
    );
    match block.sole() {
        Ok(Some(NodeContent::Sequence(seq))) => {
            assert_eq!(seq.visible_len(), 0, "empty of its kind, honestly");
        }
        other => panic!("expected the empty sequence content, got {other:?}"),
    }
}

#[test]
fn test_sole_refuses_a_plural_node_with_the_witness() {
    // Two replicas concurrently decide what one block is. Nothing is
    // discarded (the product law), the plurality is surfaced (the read), and
    // the checked projection refuses instead of guessing (the typed
    // cross-kind refusal the parallel-maps recipe lacked).
    let mut a = Author::new(1);
    let mut b = Author::new(2);

    let (_, _) = a.compose(|dot| (page_with(7, tag_block(dot, Kind::Register)), DotSet::new()));
    sync(&a, &mut b);

    // Concurrent: each re-tags the block, superseding only the original tag
    // write both observed; neither supersedes the other.
    let (_, _) = a.compose_super(
        |dot| page_with(7, tag_block(dot, Kind::Register)),
        |held| {
            held.children()
                .get(&7)
                .map(TestNode::observed)
                .unwrap_or_default()
        },
    );
    let (_, _) = b.compose_super(
        |dot| page_with(7, tag_block(dot, Kind::Sequence)),
        |held| {
            held.children()
                .get(&7)
                .map(TestNode::observed)
                .unwrap_or_default()
        },
    );
    sync(&a, &mut b);
    sync(&b, &mut a);
    sync(&a, &mut b);
    assert_eq!(a.state(), b.state(), "converged");

    let block = a.state().store().children().get(&7).expect("alive");
    let kinds = block.kinds_present();
    assert_eq!(kinds.len(), 2, "both concurrent kinds survive, surfaced");
    match block.sole() {
        Err(KindPlurality { kinds: witnessed }) => assert_eq!(witnessed, kinds),
        other => panic!("expected the plurality refusal, got {other:?}"),
    }
    assert_eq!(
        block.tag().values().copied().collect::<Vec<_>>(),
        [Kind::Register, Kind::Sequence],
        "the tag register carries both siblings, ascending by dot"
    );
}

#[test]
fn test_no_evidence_reads_none_and_residue_is_not_evidence() {
    // Bottom: no evidence at all.
    let node = TestNode::new();
    assert!(matches!(node.sole(), Ok(None)));
    assert!(node.kinds_present().is_empty());

    // Ordering residue: weave then supersede everything. The skeleton
    // survives (the grow-only Rhapsody posture), so the node is NOT bottom,
    // but a tombstone is recording, not content: no kind is in evidence.
    let mut pair: Dotted<TestNode> = Dotted::new();
    pair.merge_from(&Dotted::from_store(seq_block(dot(1, 1), 1)));
    let mut superseded = DotSet::new();
    assert!(superseded.insert(dot(1, 1)));
    pair.merge_from(&Dotted::from_context(superseded));

    let node = pair.store();
    assert!(!node.is_bottom(), "the skeleton is state a merge must keep");
    assert_eq!(node.sequence().skeleton_len(), 1);
    assert!(
        node.kinds_present().is_empty(),
        "kind evidence rides surviving support, never the recording"
    );
    assert!(matches!(node.sole(), Ok(None)));
}

#[test]
fn test_nested_residue_does_not_evidence_map() {
    // The residue rule, applied one level up (the S190 gate-review
    // refinement): a child kept alive only by its sequence skeleton (all
    // support superseded) keeps its key in the map, because the skeleton is
    // state a merge must keep, but it is recording, not content, so the
    // parent gains no Map evidence from it.
    let mut page: Dotted<TestNode> = Dotted::new();
    page.merge_from(&Dotted::from_store(page_with(7, seq_block(dot(1, 1), 1))));
    let mut superseded = DotSet::new();
    assert!(superseded.insert(dot(1, 1)));
    page.merge_from(&Dotted::from_context(superseded));

    let node = page.store();
    assert!(
        node.children().get(&7).is_some(),
        "the key survives on the residue"
    );
    assert!(
        node.kinds_present().is_empty(),
        "a residue-only child is not Map evidence"
    );
    assert!(matches!(node.sole(), Ok(None)));
}