Struct crdts::vclock::VClock

pub struct VClock<A: Ord> {
    pub dots: BTreeMap<A, u64>,
}

A VClock is a standard vector clock. It contains a set of "actors" and associated counters. When a particular actor witnesses a mutation, their associated counter in a VClock is incremented. VClock is typically used as metadata for associated application data, rather than as the container for application data. VClock just tracks causality. It can tell you if something causally descends something else, or if different replicas are "concurrent" (were mutated in isolation, and need to be resolved externally).

Fields

dots: BTreeMap<A, u64>

dots is the mapping from actors to their associated counters

Implementations

impl<A: Ord> VClock<A>

pub fn new() -> Self

Returns a new VClock instance.

pub fn clone_without(&self, base_clock: &VClock<A>) -> VClock<A> where
    A: Clone, 

Returns a clone of self but with information that is older than given clock is forgotten

pub fn inc(&self, actor: A) -> Dot<A> where
    A: Clone, 

Generate Op to increment an actor's counter.

Examples

use crdts::{VClock, CmRDT};
let mut a = VClock::new();

// `a.inc()` does not mutate the vclock!
let op = a.inc("A");
assert_eq!(a, VClock::new());

// we must apply the op to the VClock to have
// its edit take effect.
a.apply(op.clone());
assert_eq!(a.get(&"A"), 1);

// Op's can be replicated to another node and
// applied to the local state there.
let mut other_node = VClock::new();
other_node.apply(op);
assert_eq!(other_node.get(&"A"), 1);

pub fn get(&self, actor: &A) -> u64

Return the associated counter for this actor. All actors not in the vclock have an implied count of 0

pub fn dot(&self, actor: A) -> Dot<A>

Return the Dot for a given actor

pub fn concurrent(&self, other: &VClock<A>) -> bool

True if two vector clocks have diverged.

Examples

use crdts::{VClock, CmRDT};
let (mut a, mut b) = (VClock::new(), VClock::new());
a.apply(a.inc("A"));
b.apply(b.inc("B"));
assert!(a.concurrent(&b));

pub fn is_empty(&self) -> bool

Returns true if this vector clock contains nothing.

pub fn intersection(left: &VClock<A>, right: &VClock<A>) -> VClock<A> where
    A: Clone, 

Returns the common elements (same actor and counter) for two VClock instances.

pub fn glb(&mut self, other: &Self)

Reduces this VClock to the greatest-lower-bound of the given VClock and itsef, as an example see the following code.

use crdts::{VClock, Dot, ResetRemove, CmRDT};
let mut c = VClock::new();
c.apply(Dot::new(23, 6));
c.apply(Dot::new(89, 14));
let c2 = c.clone();

c.glb(&c2); // this is a no-op since `glb { c, c } = c`
assert_eq!(c, c2);

c.apply(Dot::new(43, 1));
assert_eq!(c.get(&43), 1);
c.glb(&c2); // should remove the 43 => 1 entry
assert_eq!(c.get(&43), 0);

pub fn iter(&self) -> impl Iterator<Item = Dot<&A>>

Returns an iterator over the dots in this vclock

Trait Implementations

impl<A: Ord + Clone + Debug + Arbitrary> Arbitrary for VClock<A>

pub fn arbitrary<G: Gen>(g: &mut G) -> Self

pub fn shrink(&self) -> Box<dyn Iterator<Item = Self>>

impl<A: Clone + Ord> Clone for VClock<A>

pub fn clone(&self) -> VClock<A>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<A: Ord + Clone + Debug> CmRDT for VClock<A>

type Op = Dot<A>

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.

type Validation = DotRange<A>

The validation error returned by validate_op.

pub fn validate_op(&self, dot: &Self::Op) -> Result<(), Self::Validation>

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.

pub fn apply(&mut self, dot: Self::Op)

Monotonically adds the given actor version to this VClock.

Examples

use crdts::{VClock, Dot, CmRDT};
let mut v = VClock::new();

v.apply(Dot::new("A", 2));

// now all dots applied to `v` from actor `A` where
// the counter is not bigger than 2 are nops.
v.apply(Dot::new("A", 0));
assert_eq!(v.get(&"A"), 2);

impl<A: Ord + Clone + Debug> CvRDT for VClock<A>

type Validation = VacuousValidation

The validation error returned by validate_merge.

pub fn validate_merge(&self, _other: &Self) -> Result<(), Self::Validation>

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.

pub fn merge(&mut self, other: Self)

Merge the given CRDT into the current CRDT.

impl<A: Debug + Ord> Debug for VClock<A>

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<A: Ord> Default for VClock<A>

pub fn default() -> Self

Returns the "default value" for a type.

impl<'de, A: Ord> Deserialize<'de> for VClock<A> where
    A: Deserialize<'de>, 

pub fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl<A: Ord + Display> Display for VClock<A>

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<A: Eq + Ord> Eq for VClock<A>

impl<A: Ord + Clone + Debug> From<Dot<A>> for VClock<A>

pub fn from(dot: Dot<A>) -> Self

Performs the conversion.

impl<A: Ord + Clone + Debug> FromIterator<Dot<A>> for VClock<A>

pub fn from_iter<I: IntoIterator<Item = Dot<A>>>(iter: I) -> Self

Creates a value from an iterator.

impl<A: Hash + Ord> Hash for VClock<A>

pub fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<A: Ord> IntoIterator for VClock<A>

type Item = Dot<A>

The type of the elements being iterated over.

type IntoIter = IntoIter<A>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> Self::IntoIter

Consumes the vclock and returns an iterator over dots in the clock

impl<A: PartialEq + Ord> PartialEq<VClock<A>> for VClock<A>

pub fn eq(&self, other: &VClock<A>) -> bool

This method tests for self and other values to be equal, and is used by ==.

pub fn ne(&self, other: &VClock<A>) -> bool

This method tests for !=.

impl<A: Ord> PartialOrd<VClock<A>> for VClock<A>

pub fn partial_cmp(&self, other: &VClock<A>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]pub fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<A: Ord> ResetRemove<A> for VClock<A>

pub fn reset_remove(&mut self, other: &Self)

Forget any actors that have smaller counts than the count in the given vclock

impl<A: Ord> Serialize for VClock<A> where
    A: Serialize, 

pub fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl<A: Ord> StructuralEq for VClock<A>

impl<A: Ord> StructuralPartialEq for VClock<A>