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>

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

Return an arbitrary value.

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

Return an iterator of values that are smaller than itself.

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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);

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.

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.

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

type Validation = Infallible

The validation error returned by validate_merge.

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.

fn merge(&mut self, other: Self)

Merge the given CRDT into the current CRDT.

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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

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>

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

Formats the value using the given formatter.

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

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

Converts to this type from the input type.

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

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>

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

Feeds this value into the given Hasher.

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

Feeds a slice of this type into the given Hasher.

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

fn into_iter(self) -> Self::IntoIter

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

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?

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

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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

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

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

fn lt(&self, other: &Rhs) -> bool

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

fn le(&self, other: &Rhs) -> bool

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

fn gt(&self, other: &Rhs) -> bool

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

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>

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

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

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

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

Serialize this value into the given Serde serializer.

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

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

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