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

extern crate alloc;

use alloc::collections::BTreeMap;
use alloc::vec::Vec;

use crate::kairos::Kairos;
use crate::metis::{Anchor, DotStore, Locus, Rhapsody};

use super::Dot;

/// The naive reference order, built independently of `Rhapsody::order`.
pub(super) fn reference_order(rhapsody: &Rhapsody) -> Vec<Dot> {
    enum Frame {
        Visit(Dot),
        Emit(Dot),
    }

    // Reconstruct the reachable skeleton through public reads, chasing visible
    // dots' anchors up to the origin.
    let mut loci: BTreeMap<Dot, Locus> = BTreeMap::new();
    let mut frontier: Vec<Dot> = rhapsody.dots().collect();
    while let Some(dot) = frontier.pop() {
        if loci.contains_key(&dot) {
            continue;
        }
        if let Some(locus) = rhapsody.locus(dot) {
            let _ = loci.insert(dot, locus);
            // An anchor is a raw coordinate; one naming the non-dot zero
            // names no locus, so it never joins the frontier (R-91).
            if let Some(Ok(anchor)) = locus.anchor.dot().map(Dot::try_from) {
                frontier.push(anchor);
            }
        }
    }

    let mut children: BTreeMap<Anchor, Vec<Dot>> = BTreeMap::new();
    for (&dot, locus) in &loci {
        children.entry(locus.anchor).or_default().push(dot);
    }
    for bucket in children.values_mut() {
        bucket.sort_by(|a, b| {
            let (ra, rb): (Kairos, Kairos) = (loci[a].rank, loci[b].rank);
            rb.cmp(&ra).then_with(|| a.cmp(b))
        });
    }

    let mut order = Vec::new();
    let mut stack: Vec<Frame> = children
        .get(&Anchor::Origin)
        .map(|roots| roots.iter().rev().map(|&d| Frame::Visit(d)).collect())
        .unwrap_or_default();
    while let Some(frame) = stack.pop() {
        match frame {
            Frame::Emit(dot) => {
                if rhapsody.is_visible(dot) {
                    order.push(dot);
                }
            }
            Frame::Visit(dot) => {
                if let Some(kids) = children.get(&Anchor::After(dot.into())) {
                    for &kid in kids.iter().rev() {
                        stack.push(Frame::Visit(kid));
                    }
                }
                stack.push(Frame::Emit(dot));
                if let Some(kids) = children.get(&Anchor::Before(dot.into())) {
                    for &kid in kids {
                        stack.push(Frame::Visit(kid));
                    }
                }
            }
        }
    }
    order
}