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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

use crate::traits::Grow;

/// A vectorized counter that can only grow
///
/// # Panics
///
/// Any function involving two or more `GCounter`s (viz. `le` and `merge`) will panic (via
/// `assert_eq!`) if their counts vectors are not the same length. I'd prefer to check this at
/// compile time (as much as possible) instead, but
///
/// - avoiding C++'s template mess is part of what makes Rust great
/// - Rust doesn't have [const generics](https://rust-lang.github.io/rfcs/2000-const-generics.html)
/// yet
/// - this library is meant to be as simple and expository as possible, so I'd like to avoid
/// fancier things like [`generic_array`](https://docs.rs/generic-array/0.14.4/generic_array/)
///
/// As mentioned above, operations panic when trying dealing with two or more `GCounter`s of
/// incompatible sizes:
///
/// ```should_panic
/// // this will panic
/// use cvrdt_exposition::{GCounter, Grow};
/// let x = GCounter::new((0, vec![0]));
/// let y = GCounter::new((1, vec![0, 0]));
/// x.merge(&y);
/// ```
///
/// # Difference from references
///
/// In the [comprehensive study paper](https://hal.inria.fr/inria-00555588/) and the [Wikipedia
/// article](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type), the vectorized
/// `GCounter` presumes a local `myID()` function that tells our local `GCounter` the index to
/// update in its counts array. This detail isn't necessary for understanding how their pseudocode
/// works, but it _is_ required if you're trying to implement a `GCounter` in real code. As such,
/// we explicitly include the `id` as a member of our `GCounter` struct, and make the _arbitrary_
/// choice that when merging two `GCounter`s, we take the minimum of their two `id`s as the new
/// one.
///
/// # Examples
///
/// Example usage, including demonstrating some properties:
///
/// ```
/// use cvrdt_exposition::{GCounter, Grow};
/// let mut x = GCounter::new((0, vec![0; 3]));
/// x.add(());
/// assert_eq!(x.payload(), (0, vec![1, 0, 0]));
/// assert_eq!(x.query(&()), 1);
/// let mut y = GCounter::new((1, vec![0; 3]));
/// y.add(());
/// y.add(());
/// assert_eq!(x.merge(&y).payload(), (0, vec![1, 2, 0]));
/// let z = GCounter::new((2, vec![0, 0, 3]));
/// assert!(x.le(&x.merge(&y).merge(&z)));
/// assert_eq!(x.merge(&y).merge(&z).payload(), (0, vec![1, 2, 3]));
/// assert_eq!(x.merge(&y.merge(&z)).payload(), x.merge(&y).merge(&z).payload());
/// ```
#[derive(Debug, Clone)]
pub struct GCounter {
    /// The index for this local `GCounter` where all increments occur
    pub id: usize,
    /// The vector of counts
    pub counts: Vec<u64>,
}

impl GCounter {
    fn compatible_len(&self, other: &Self) -> usize {
        assert_eq!(
            self.counts.len(),
            other.counts.len(),
            "Incompatible lengths"
        );
        self.counts.len()
    }
}

impl Grow for GCounter {
    type Payload = (usize, Vec<u64>);
    type Update = ();
    type Query = ();
    type Value = u64;

    fn new(payload: Self::Payload) -> Self {
        GCounter {
            id: payload.0,
            counts: payload.1,
        }
    }
    fn payload(&self) -> Self::Payload {
        (self.id, self.counts.clone())
    }
    fn add(&mut self, _update: Self::Update) {
        self.counts[self.id] += 1;
    }
    fn le(&self, other: &Self) -> bool {
        let n = self.compatible_len(other);
        (0..n).all(|i| self.counts[i] <= other.counts[i])
    }
    fn merge(&self, other: &Self) -> Self {
        let n = self.compatible_len(other);
        GCounter {
            id: self.id.min(other.id), // arbitrary
            counts: (0..n)
                .map(|i| self.counts[i].max(other.counts[i]))
                .collect(),
        }
    }
    fn query(&self, _query: &Self::Query) -> Self::Value {
        self.counts.iter().sum()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::grow_properties;
    use proptest::prelude::*;

    static MAX_SIZE: usize = 100;

    fn sized(n: usize) -> impl Strategy<Value = GCounter> {
        prop::collection::vec(any::<u64>(), n)
            .prop_flat_map(|counts| {
                let len = counts.len();
                (0..len, Just(counts))
            })
            .prop_map(|(id, counts)| GCounter { id, counts })
    }

    fn two() -> impl Strategy<Value = (GCounter, GCounter)> {
        (1..MAX_SIZE).prop_flat_map(|n| (sized(n), sized(n)))
    }
    fn three() -> impl Strategy<Value = (GCounter, GCounter, GCounter)> {
        (1..MAX_SIZE).prop_flat_map(|n| (sized(n), sized(n), sized(n)))
    }
    fn cvrdt_and_update() -> impl Strategy<Value = (GCounter, ())> {
        (1..MAX_SIZE).prop_flat_map(sized).prop_map(|g| (g, ()))
    }

    grow_properties!(two, three, cvrdt_and_update);
}