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

//! A foreign, value-carrying [`DotStore`] exercised from the outside, the way
//! a future collaborative editor would (S99, tests only).
//!
//! [`Inscribed`] is a dot-to-value map: the multi-value register store shape
//! from the delta-CRDT literature. It implements the open axis for a caller's
//! own value type through the public trait alone. The child modules drive the
//! generic `DotStore` laws and the end-to-end register recipe over
//! `Dotted<Inscribed>`.

extern crate alloc;

use alloc::collections::{BTreeMap, BTreeSet};
use alloc::string::String;

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

mod laws;
mod register;

/// A dot-to-value map. A dot names one write, so concurrent writes are distinct
/// dots that both survive as the multi-value read.
#[derive(Clone, Debug, PartialEq, Eq, Default)]
struct Inscribed {
    /// Per dot, the caller's value. Bottom is the empty map.
    entries: BTreeMap<Dot, String>,
}

impl Inscribed {
    /// Builds a store from already-keyed entries.
    fn from_entries(entries: BTreeMap<Dot, String>) -> Self {
        Self { entries }
    }

    /// A one-dot store: `value` under `dot`, nothing else.
    fn singleton(dot: Dot, value: String) -> Self {
        let mut entries = BTreeMap::new();
        let _ = entries.insert(dot, value);
        Self { entries }
    }

    /// The value under a dot, if the store carries it.
    fn value(&self, dot: Dot) -> Option<&String> {
        self.entries.get(&dot)
    }

    /// Whether the store carries `dot`.
    fn holds(&self, dot: Dot) -> bool {
        self.entries.contains_key(&dot)
    }
}

impl DotStore for Inscribed {
    fn dots(&self) -> impl Iterator<Item = Dot> + '_ {
        self.entries.keys().copied()
    }

    fn is_bottom(&self) -> bool {
        self.entries.is_empty()
    }

    fn causal_merge(&self, self_context: &DotSet, other: &Self, other_context: &DotSet) -> Self {
        let mut entries = BTreeMap::new();
        for (&dot, value) in &self.entries {
            let in_both = other.holds(dot);
            if Self::survives(in_both, other_context.contains(dot)) {
                let _ = entries.insert(dot, value.clone());
            }
        }
        for (&dot, value) in &other.entries {
            if self.holds(dot) {
                continue;
            }
            if Self::survives(false, self_context.contains(dot)) {
                let _ = entries.insert(dot, value.clone());
            }
        }
        Self { entries }
    }

    fn restrict(&self, roster: impl IntoIterator<Item = u32>) -> Self {
        let roster: BTreeSet<u32> = roster.into_iter().collect();
        let entries = self
            .entries
            .iter()
            .filter(|(dot, _)| roster.contains(&dot.station()))
            .map(|(&key, value)| (key, value.clone()))
            .collect();
        Self { entries }
    }

    fn novel_to(&self, context: &DotSet) -> Self {
        let entries = self
            .entries
            .iter()
            .filter(|(dot, _)| !context.contains(**dot))
            .map(|(&key, value)| (key, value.clone()))
            .collect();
        Self { entries }
    }
}