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

extern crate alloc;

use super::model::Record;
use crate::kairos::Kairos;
use crate::metis::{Anchor, Dot, Locus};
use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;

pub(super) fn reference_order(record: &Record) -> Vec<Dot> {
    enum Frame {
        Visit(Dot),
        Emit(Dot),
    }

    let woven: &BTreeMap<Dot, Locus> = &record.woven;
    // Group every child under its anchor once (the record is the only
    // input, so the oracle stays independent of the production planes; the
    // grouping only retires the per-visit whole-record rescan, which the
    // paste-bearing model made quadratic in practice).
    let mut buckets: BTreeMap<Anchor, Vec<Dot>> = BTreeMap::new();
    for (&dot, locus) in woven {
        buckets.entry(locus.anchor).or_default().push(dot);
    }
    for kids in buckets.values_mut() {
        kids.sort_by(|a, b| {
            let (ra, rb): (Kairos, Kairos) = (woven[a].rank, woven[b].rank);
            rb.cmp(&ra).then_with(|| a.cmp(b))
        });
    }
    let bucket = |anchor: Anchor| -> Vec<Dot> { buckets.get(&anchor).cloned().unwrap_or_default() };

    let mut order = Vec::new();
    let mut stack: Vec<Frame> = bucket(Anchor::Origin)
        .into_iter()
        .rev()
        .map(Frame::Visit)
        .collect();
    while let Some(frame) = stack.pop() {
        match frame {
            Frame::Emit(dot) => {
                if !record.expelled.contains(&dot) {
                    order.push(dot);
                }
            }
            Frame::Visit(dot) => {
                for kid in bucket(Anchor::After(dot.into())).into_iter().rev() {
                    stack.push(Frame::Visit(kid));
                }
                stack.push(Frame::Emit(dot));
                for kid in bucket(Anchor::Before(dot.into())) {
                    stack.push(Frame::Visit(kid));
                }
            }
        }
    }
    order
}

#[test]
fn test_reference_handles_the_empty_run() {
    let record = Record {
        woven: BTreeMap::new(),
        expelled: BTreeSet::new(),
    };
    assert_eq!(reference_order(&record), Vec::<Dot>::new());
}