crdt_tree/
clock.rs

1// Copyright (c) 2022, MaidSafe.
2// All rights reserved.
3//
4// This SAFE Network Software is licensed under the BSD-3-Clause license.
5// Please see the LICENSE file for more details.
6
7use crdts::quickcheck::{Arbitrary, Gen};
8use serde::{Deserialize, Serialize};
9use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
10
11use crdts::Actor;
12use std::hash::{Hash, Hasher};
13
14/// Implements a `Lamport Clock` consisting of an `Actor` and an integer counter.
15#[derive(Debug, Clone, Serialize, Deserialize)]
16pub struct Clock<A: Actor> {
17    actor_id: A,
18    counter: u64,
19}
20
21impl<A: Actor> Clock<A> {
22    /// create new Clock instance
23    ///
24    /// typically counter should be None
25    pub fn new(actor_id: A, counter: Option<u64>) -> Self {
26        Self {
27            actor_id,
28            counter: counter.unwrap_or(0),
29        }
30    }
31
32    /// returns a new Clock with same actor but counter incremented by 1.
33    pub fn inc(&self) -> Self {
34        Self::new(self.actor_id.clone(), Some(self.counter.saturating_add(1)))
35    }
36
37    /// increments clock counter and returns a clone
38    pub fn tick(&mut self) -> Self {
39        self.counter = self.counter.saturating_add(1);
40        self.clone()
41    }
42
43    /// returns actor_id reference
44    #[inline]
45    pub fn actor_id(&self) -> &A {
46        &self.actor_id
47    }
48
49    /// returns counter
50    #[inline]
51    pub fn counter(&self) -> u64 {
52        self.counter
53    }
54
55    /// returns a new Clock with same actor but counter is
56    /// max(this_counter, other_counter)
57    pub fn merge(&self, other: &Self) -> Self {
58        Self::new(
59            self.actor_id.clone(),
60            Some(std::cmp::max(self.counter, other.counter)),
61        )
62    }
63}
64
65impl<A: Actor> Ord for Clock<A> {
66    /// compares this Clock with another.
67    /// if counters are unequal, returns -1 or 1 accordingly.
68    /// if counters are equal, returns -1, 0, or 1 based on actor_id.
69    ///    (this is arbitrary, but deterministic.)
70    fn cmp(&self, other: &Self) -> Ordering {
71        match self.counter.cmp(&other.counter) {
72            Ordering::Equal => self.actor_id.cmp(&other.actor_id),
73            Ordering::Greater => Ordering::Greater,
74            Ordering::Less => Ordering::Less,
75        }
76    }
77}
78
79impl<A: Actor> PartialOrd for Clock<A> {
80    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
81        Some(self.cmp(other))
82    }
83}
84
85impl<A: Actor> PartialEq for Clock<A> {
86    fn eq(&self, other: &Self) -> bool {
87        self.cmp(other) == Ordering::Equal
88    }
89}
90
91impl<A: Actor> Eq for Clock<A> {}
92
93impl<A: Actor> Hash for Clock<A> {
94    fn hash<H: Hasher>(&self, state: &mut H) {
95        self.actor_id.hash(state);
96        self.counter.hash(state);
97    }
98}
99
100// Generate arbitrary (random) clocks.  needed by quickcheck.
101impl<A: Actor + Arbitrary> Arbitrary for Clock<A> {
102    fn arbitrary<G: Gen>(g: &mut G) -> Self {
103        Self {
104            actor_id: A::arbitrary(g),
105            counter: u64::arbitrary(g),
106        }
107    }
108
109    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
110        let mut shrunk_clocks = Vec::new();
111        if self.counter > 0 {
112            shrunk_clocks.push(Self::new(self.actor_id.clone(), Some(self.counter - 1)));
113        }
114        Box::new(shrunk_clocks.into_iter())
115    }
116}
117
118#[cfg(test)]
119mod test {
120    use super::*;
121    use quickcheck::quickcheck;
122
123    quickcheck! {
124        fn inc_increments_only_the_counter(clock: Clock<u8>) -> bool {
125            clock.inc() == Clock::new(clock.actor_id, Some(clock.counter + 1))
126        }
127
128        fn test_total_order(a: Clock<u8>, b: Clock<u8>) -> bool {
129            let cmp_ab = a.cmp(&b);
130            let cmp_ba = b.cmp(&a);
131
132            match (cmp_ab, cmp_ba) {
133                (Ordering::Less, Ordering::Greater) => a.counter < b.counter || a.counter == b.counter && a.actor_id < b.actor_id,
134                (Ordering::Greater, Ordering::Less) => a.counter > b.counter || a.counter == b.counter && a.actor_id > b.actor_id,
135                (Ordering::Equal, Ordering::Equal) => a.actor_id == b.actor_id && a.counter == b.counter,
136                _ => false,
137            }
138        }
139
140        fn test_partial_order(a: Clock<u8>, b: Clock<u8>) -> bool {
141            let cmp_ab = a.partial_cmp(&b);
142            let cmp_ba = b.partial_cmp(&a);
143
144            match (cmp_ab, cmp_ba) {
145                (None, None) => a.actor_id != b.actor_id,
146                (Some(Ordering::Less), Some(Ordering::Greater)) => a.counter < b.counter || a.counter == b.counter && a.actor_id < b.actor_id,
147                (Some(Ordering::Greater), Some(Ordering::Less)) => a.counter > b.counter || a.counter == b.counter && a.actor_id > b.actor_id,
148                (Some(Ordering::Equal), Some(Ordering::Equal)) => a.actor_id == b.actor_id && a.counter == b.counter,
149                _ => false
150            }
151        }
152    }
153}
crdt_tree/clock.rs

crdt_tree/
clock.rs
