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

use std::error::Error;
use std::hash::Hash;

use crate::VClock;

/// Common Actor type. Actors are unique identifier for every `thing` mutating a VClock.
/// VClock based CRDT's will need to expose this Actor type to the user.
pub trait Actor: Ord + Clone + Hash {}
impl<A: Ord + Clone + Hash> Actor for A {}

/// State based CRDT's replicate by transmitting the entire CRDT state.
pub trait CvRDT {
    /// The validation error returned by `validate_merge`.
    type Validation: Error;

    /// Some CRDT's have stricter requirements on how they must be used.
    /// To avoid violating these requirements, CRDT's provide an interface
    /// to optionally validate merge compatibility before attempting to merge.
    ///
    /// An `Ok(())` response signals that the merge is safe to proceed.
    /// Otherwise a structured error is returned to help you determine what
    /// is wrong with the merge.
    fn validate_merge(&self, other: &Self) -> Result<(), Self::Validation>;

    /// Merge the given CRDT into the current CRDT.
    fn merge(&mut self, other: Self);
}

/// Operation based CRDT's replicate by transmitting each operation.
pub trait CmRDT {
    /// Op defines a mutation to the CRDT.
    /// As long as Op's from one actor are replayed in exactly the same order they
    /// were generated by that actor, the CRDT will converge. In other words, we must
    /// have a total ordering on each actors operations, while requiring only a partial
    /// order over all ops.
    /// E.g.
    ///
    /// * Actor A produces ops A1, A2
    /// * Actor B produces ops B1, B2
    ///
    /// the only valid orderings are:
    /// * A1 < A2 < B1 < B2
    /// * A1 < B1 < A2 < B2
    /// * B1 < A1 < A2 < B2
    /// * A1 < B1 < B2 < A2
    /// * B1 < A1 < B2 < A2
    /// * B1 < B2 < A1 < A2
    ///
    /// Applying ops in any of the valid orders will converge to the same CRDT state
    ///
    /// Op's must be idempotent, meaning any Op may be applied more than once.
    type Op;

    /// The validation error returned by `validate_op`.
    type Validation: Error;

    /// Some CRDT's have stricter requirements on how they must be used.
    /// To avoid violating these requirements, CRDT's provide an interface
    /// to optionally validate op's before they are applied.
    ///
    /// An `Ok(())` response signals that this operation is safe to apply.
    /// Otherwise a structured error is returned to help you determine what
    /// is wrong with the operation
    fn validate_op(&self, op: &Self::Op) -> Result<(), Self::Validation>;

    /// Apply an Op to the CRDT
    fn apply(&mut self, op: Self::Op);
}

/// CRDT's are causal if they are built on top of vector clocks.
pub trait ResetRemove<A: Ord> {
    /// Remove data that is strictly smaller than this clock
    fn reset_remove(&mut self, clock: &VClock<A>);
}