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

extern crate alloc;

use crate::kairos::{Clock, TickCounter};
use crate::metis::{Anchor, Dot, DotSet, Dotted, Locus, Rhapsody};

mod condense;
mod conformance;
mod core;
mod extent;
mod positional;
mod run;
mod visual;
mod walk;

/// A rhapsody carried by a causal pair, the way a replica holds one.
type Seq = Dotted<Rhapsody>;

/// Builds a fresh clock for `station`, the test-support way (station >= 1).
fn clock(station: u32) -> Clock<TickCounter> {
    Clock::with_default_config(TickCounter::new(), station).unwrap()
}

/// A one-element rhapsody delta: `dot` woven at `locus`, with the dot as its own
/// context (a covered pure-write pair).
fn woven(dot: Dot, locus: Locus) -> Seq {
    let mut rhapsody = Rhapsody::new();
    assert!(rhapsody.weave(dot, locus));
    Dotted::from_store(rhapsody)
}

/// The documented insert flow: assign a fresh dot for `station`, mint its
/// rank from the replica's own clock, weave it after `anchor`, merge, return
/// the dot.
fn insert(replica: &mut Seq, clk: &Clock<TickCounter>, station: u32, anchor: Option<Dot>) -> Dot {
    let dot = replica.next_dot(station);
    let locus = Locus {
        anchor: anchor.map_or(Anchor::Origin, |dot| Anchor::After(dot.into())),
        rank: clk.now(0u16),
    };
    *replica = replica.merge(&woven(dot, locus));
    dot
}

/// Weaves a fresh element for `station` at an explicit `anchor`, minting the
/// rank off `clk` (each call ticks once, so successive calls at the same anchor
/// ascend in rank). Returns the new dot. The direct-anchor analog of `insert`.
fn weave_at(replica: &mut Seq, clk: &Clock<TickCounter>, station: u32, anchor: Anchor) -> Dot {
    let dot = replica.next_dot(station);
    let locus = Locus {
        anchor,
        rank: clk.now(0u16),
    };
    *replica = replica.merge(&woven(dot, locus));
    dot
}

/// One insert-before at the document start: place a fresh element for `station`
/// at the slot before the current head, through the visual-insert seam. The seam
/// returns `Origin` on an empty document (a top rank reads first) and
/// `Before(head)` once a head exists; either way the caller mints a rank above
/// the returned anchor's bucket so the element reads at the document start. This
/// is the honest "type a run backwards" motion the B.2 scenario needs.
fn prepend(replica: &mut Seq, clk: &Clock<TickCounter>, station: u32) -> Dot {
    let anchor = replica.store().anchor_for_visual_insert(None);
    // Mint above the returned bucket's head (the rank a newcomer must beat to
    // land adjacent to the anchor), exactly the visual-insert discipline.
    if let Some(top) = replica.store().children_of(anchor).next()
        && let Some(locus) = replica.store().locus(top)
    {
        clk.observe(locus.rank);
    }
    weave_at(replica, clk, station, anchor)
}

/// The documented delete flow: supersede exactly `dot` (a pure-context pair).
fn delete(replica: &mut Seq, dot: Dot) {
    let mut ctx = DotSet::new();
    assert!(ctx.insert(dot));
    *replica = replica.merge(&Dotted::from_context(ctx));
}

/// The start index of `run` inside `seq` as a contiguous slice, if present.
fn position_of_run(seq: &[Dot], run: &[Dot]) -> Option<usize> {
    if run.is_empty() {
        return Some(0);
    }
    seq.windows(run.len()).position(|w| w == run)
}