Struct State 

pub struct State<ID: TreeId, TM: TreeMeta, A: Actor> { /* private fields */ }

Holds Tree CRDT state and implements the core algorithm.

State is not tied to any actor/peer and should be equal on any two replicas where each has applied the same operations.

State may be instantiated to manipulate a CRDT Tree or alternatively the higher level TreeReplica may be used.

For usage/examples, see: tests/tree.rs

This code aims to be an accurate implementation of the tree crdt algorithm described in:

“A highly-available move operation for replicated trees and distributed filesystems” [1] by Martin Klepmann, et al.

[1] https://martin.kleppmann.com/papers/move-op.pdf

Implementations

impl<ID: TreeId, TM: TreeMeta, A: Actor> State<ID, TM, A>

pub fn new() -> Self

create a new State

pub fn tree(&self) -> &Tree<ID, TM>

returns tree reference

pub fn tree_mut(&mut self) -> &mut Tree<ID, TM>

returns mutable Tree reference

Warning: this is dangerous. Normally the Tree should not be mutated directly.

See the demo_move_to_trash in examples/demo.rs for a use-case, only after log truncation has been performed.

pub fn log(&self) -> &Vec<LogOpMove<ID, TM, A>>

returns log reference

Examples found in repository

examples/demo.rs (line 260)

fn demo_truncate_log() {
    let mut replicas: Vec<TreeReplica<TypeId, TypeMeta, TypeActor>> = Vec::new();
    let num_replicas = 5;

    // start some replicas.
    for _i in 0..num_replicas {
        // pass true flag to enable causally stable threshold tracking
        let r: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
        replicas.push(r);
    }

    let root_id = new_id();

    // Generate initial tree state.
    let mut opmoves = vec![replicas[0].opmove(0, "root", root_id)];

    println!("generating move operations...");

    // generate some initial ops from all replicas.
    for r in replicas.iter_mut() {
        let finaldepth = rand::thread_rng().gen_range(3, 6);
        let mut ops = vec![];
        mktree_ops(&mut ops, r, root_id, 2, finaldepth);
        opmoves.extend(r.opmoves(ops));
    }

    // apply all ops to all replicas
    println!(
        "applying {} operations to all {} replicas...\n",
        opmoves.len(),
        replicas.len()
    );
    apply_ops_to_replicas(&mut replicas, &opmoves);

    #[derive(Debug)]
    #[allow(dead_code)]
    struct Stat {
        pub replica: TypeActor,
        pub ops_before_truncate: usize,
        pub ops_after_truncate: usize,
    }

    let mut stats: Vec<Stat> = Vec::new();
    for r in replicas.iter_mut() {
        println!("truncating log of replica {}...", r.id());
        println!(
            "causally stable threshold: {:?}\n",
            r.causally_stable_threshold()
        );
        let ops_b4 = r.state().log().len();
        r.truncate_log();
        let ops_after = r.state().log().len();
        stats.push(Stat {
            replica: *r.id(),
            ops_before_truncate: ops_b4,
            ops_after_truncate: ops_after,
        });
    }

    println!("-- Stats -- ");
    println!("\n{:#?}", stats);
}

pub fn add_log_entry(&mut self, entry: LogOpMove<ID, TM, A>)

add_log_entry

pub fn truncate_log_before(&mut self, timestamp: &Clock<A>) -> bool

removes log entries before a given timestamp. not part of crdt-tree algo.

pub fn do_op(&mut self, op: OpMove<ID, TM, A>) -> LogOpMove<ID, TM, A>

The do_op function performs the actual work of applying a move operation.

This function takes as argument a pair consisting of a Move operation and the current tree and it returns a pair consisting of a LogMove operation (which will be added to the log) and an updated tree.

pub fn undo_op(&mut self, log: &LogOpMove<ID, TM, A>)

undo_op

pub fn redo_op(&mut self, log: LogOpMove<ID, TM, A>)

redo_op uses do_op to perform an operation again and recomputes the LogMove record (which might have changed due to the effect of the new operation)

pub fn apply_op(&mut self, op1: OpMove<ID, TM, A>)

See general description of apply/undo/redo above.

The apply_op func takes two arguments: a Move operation to apply and the current replica state; and it returns the new replica state. The constrains t::{linorder} in the type signature indicates that timestamps t are instance if linorder type class, and they can therefore be compared with the < operator during a linear (or total) order.

pub fn apply_ops_into(&mut self, ops: Vec<OpMove<ID, TM, A>>)

applies a list of operations and consume them. (no cloning)

pub fn apply_ops(&mut self, ops: &[OpMove<ID, TM, A>])

applies a list of operations reference, cloning each op.

Trait Implementations

impl<ID: Clone + TreeId, TM: Clone + TreeMeta, A: Clone + Actor> Clone for State<ID, TM, A>

fn clone(&self) -> State<ID, TM, A>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<ID: TreeId, TM: TreeMeta, A: Actor> CmRDT for State<ID, TM, A>

fn apply(&mut self, op: Self::Op)

Apply an operation to a State instance.

type Op = OpMove<ID, TM, 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.

impl<ID: Debug + TreeId, TM: Debug + TreeMeta, A: Debug + Actor> Debug for State<ID, TM, A>

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

Formats the value using the given formatter.

impl<ID: TreeId, A: Actor, TM: TreeMeta> Default for State<ID, TM, A>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, ID, TM, A> Deserialize<'de> for State<ID, TM, A>

where ID: Deserialize<'de> + TreeId, TM: Deserialize<'de> + TreeMeta, A: Deserialize<'de> + Actor,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<ID: TreeId, A: Actor, TM: TreeMeta> From<(Vec<LogOpMove<ID, TM, A>>, Tree<ID, TM>)> for State<ID, TM, A>

fn from(e: (Vec<LogOpMove<ID, TM, A>>, Tree<ID, TM>)) -> Self

creates State from tuple (Vec<LogOpMove>, Tree)

impl<ID: TreeId, TM: TreeMeta, A: Actor> IntoIterator for State<ID, TM, A>

Implement IntoIterator for State. This is useful for walking all Nodes in a tree without knowing a starting point.

type Item = (ID, TreeNode<ID, TM>)

The type of the elements being iterated over.

type IntoIter = IntoIter<ID, TreeNode<ID, TM>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<ID: PartialEq + TreeId, TM: PartialEq + TreeMeta, A: PartialEq + Actor> PartialEq for State<ID, TM, A>

fn eq(&self, other: &State<ID, TM, A>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<ID, TM, A> Serialize for State<ID, TM, A>

where ID: Serialize + TreeId, TM: Serialize + TreeMeta, A: Serialize + Actor,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<ID: Eq + TreeId, TM: Eq + TreeMeta, A: Eq + Actor> Eq for State<ID, TM, A>

impl<ID: TreeId, TM: TreeMeta, A: Actor> StructuralPartialEq for State<ID, TM, A>