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::collections::{BTreeMap, BTreeSet};

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

use super::super::DotStore;
use super::DotMap;

impl<K: Ord + Clone, S: DotStore> DotStore for DotMap<K, S> {
    fn dots(&self) -> impl Iterator<Item = Dot> + '_ {
        self.entries.values().flat_map(DotStore::dots)
    }

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

    fn causal_merge(&self, self_context: &DotSet, other: &Self, other_context: &DotSet) -> Self {
        let bottom = S::default();
        let mut entries = BTreeMap::new();
        for (key, mine) in &self.entries {
            let theirs = other.entries.get(key).unwrap_or(&bottom);
            let joined = mine.causal_merge(self_context, theirs, other_context);
            if !joined.is_bottom() {
                let _ = entries.insert(key.clone(), joined);
            }
        }
        for (key, theirs) in &other.entries {
            if self.entries.contains_key(key) {
                continue;
            }
            let joined = bottom.causal_merge(self_context, theirs, other_context);
            if !joined.is_bottom() {
                let _ = entries.insert(key.clone(), joined);
            }
        }
        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_map(|(key, store)| {
                let kept = store.restrict(roster.iter().copied());
                (!kept.is_bottom()).then(|| (key.clone(), kept))
            })
            .collect();
        Self { entries }
    }

    fn novel_to(&self, context: &DotSet) -> Self {
        // Per key the nested novelty, dropping keys left bottom (canonical
        // form): the same context vouches for every level.
        let entries = self
            .entries
            .iter()
            .filter_map(|(key, store)| {
                let novel = store.novel_to(context);
                (!novel.is_bottom()).then(|| (key.clone(), novel))
            })
            .collect();
        Self { entries }
    }

    fn novel_to_witnessed(&self, context: &DotSet, recording: &DotSet) -> Self {
        // The witness threads through unchanged: a dot lives under one key
        // only (the insertion-enforced disjointness), so the flat witness
        // vouches for every level exactly as the flat context does.
        let entries = self
            .entries
            .iter()
            .filter_map(|(key, store)| {
                let novel = store.novel_to_witnessed(context, recording);
                (!novel.is_bottom()).then(|| (key.clone(), novel))
            })
            .collect();
        Self { entries }
    }
}