Struct TreeReplica 

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

TreeReplica holds tree State plus lamport timestamp (actor + counter)

It can optionally keep track of the latest timestamp for each replica which is needed for calculating the causally stable threshold which is in turn needed for log truncation.

TreeReplica is a higher-level interface to the Tree CRDT and is tied to a particular actor/peer.

State is a lower-level interface to the Tree CRDT and is not tied to any actor/peer.

Implementations

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

pub fn new(id: A) -> Self

returns new TreeReplica

Examples found in repository

examples/demo.rs (line 43)

fn demo_concurrent_moves() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["root"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/a to /root/b
    let repl1_ops = vec![r1.opmove(ids["b"], "a", ids["a"])];

    // replica_2 "simultaneously" moves /root/a to /root/c
    let repl2_ops = vec![r2.opmove(ids["c"], "a", ids["a"])];

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/c/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    //    if r1.state.is_equal(&r2.state) {
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: cycle test from the paper
//
// Tests what happen when two peers independently perform operations that would
// introduce a cycle when combined.
//
// Upon applying eachother's ops, they must converge to a common location without
// any cycles.
fn demo_concurrent_moves_cycle() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["a"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/b to /root/a,  creating /root/a/b
    let repl1_ops = r1.opmoves(vec![(ids["a"], "b", ids["b"])]);

    // replica_2 "simultaneously" moves /root/a to /root/b, creating /root/b/a
    let repl2_ops = r2.opmoves(vec![(ids["b"], "a", ids["a"])]);

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/b/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: Walk a deep tree
//
// This demonstrates creation of a deep tree which we then walk in depth-first
// fashion.
//
// This particular tree contains 2^6-1 nodes and is up to 6 levels deep.
fn demo_walk_deep_tree() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [("root", new_id())].iter().cloned().collect();

    // Generate initial tree state.
    println!("generating ops...");
    let mut ops = vec![(0, "root", ids["root"])];
    mktree_ops(&mut ops, &mut r1, ids["root"], 2, 6); //  <-- max 6 levels deep.

    println!("applying ops...");
    let ops_len = ops.len();
    r1.apply_ops_byref(&r1.opmoves(ops));

    println!("walking tree...");
    r1.tree().walk(&ids["root"], |tree, node_id, depth| {
        if true {
            let meta = match tree.find(node_id) {
                Some(tn) => format!("{:?}", tn.metadata()),
                None => format!("{:?}", node_id),
            };
            println!("{:indent$}{}", "", meta, indent = depth);
        }
    });

    println!("\nnodes in tree: {}", ops_len);
}

/// Demonstrates log truncation
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
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);
}

/// Demonstrates moving items to a Trash node outside the nominal root and then
/// emptying the trash after the log is truncated.
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

pub fn opmove( &self, parent_id: ID, metadata: TM, child_id: ID, ) -> OpMove<ID, TM, A>

Generates an OpMove

Note that OpMove::timestamp is incremented from TreeReplica::time. TreeReplica::time is not updated until ::apply_op() is called.

Therefore, multiple ops generated with this method may share the same timestamp, and only one can be sucessfully applied.

To generate multiple ops before calling ::apply_op(), use ::opmoves() instead.

Examples found in repository

examples/demo.rs (line 71)

fn demo_concurrent_moves() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["root"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/a to /root/b
    let repl1_ops = vec![r1.opmove(ids["b"], "a", ids["a"])];

    // replica_2 "simultaneously" moves /root/a to /root/c
    let repl2_ops = vec![r2.opmove(ids["c"], "a", ids["a"])];

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/c/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    //    if r1.state.is_equal(&r2.state) {
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: cycle test from the paper
//
// Tests what happen when two peers independently perform operations that would
// introduce a cycle when combined.
//
// Upon applying eachother's ops, they must converge to a common location without
// any cycles.
fn demo_concurrent_moves_cycle() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["a"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/b to /root/a,  creating /root/a/b
    let repl1_ops = r1.opmoves(vec![(ids["a"], "b", ids["b"])]);

    // replica_2 "simultaneously" moves /root/a to /root/b, creating /root/b/a
    let repl2_ops = r2.opmoves(vec![(ids["b"], "a", ids["a"])]);

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/b/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: Walk a deep tree
//
// This demonstrates creation of a deep tree which we then walk in depth-first
// fashion.
//
// This particular tree contains 2^6-1 nodes and is up to 6 levels deep.
fn demo_walk_deep_tree() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [("root", new_id())].iter().cloned().collect();

    // Generate initial tree state.
    println!("generating ops...");
    let mut ops = vec![(0, "root", ids["root"])];
    mktree_ops(&mut ops, &mut r1, ids["root"], 2, 6); //  <-- max 6 levels deep.

    println!("applying ops...");
    let ops_len = ops.len();
    r1.apply_ops_byref(&r1.opmoves(ops));

    println!("walking tree...");
    r1.tree().walk(&ids["root"], |tree, node_id, depth| {
        if true {
            let meta = match tree.find(node_id) {
                Some(tn) => format!("{:?}", tn.metadata()),
                None => format!("{:?}", node_id),
            };
            println!("{:indent$}{}", "", meta, indent = depth);
        }
    });

    println!("\nnodes in tree: {}", ops_len);
}

/// Demonstrates log truncation
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
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);
}

/// Demonstrates moving items to a Trash node outside the nominal root and then
/// emptying the trash after the log is truncated.
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

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

Generates a list of OpMove from a list of tuples (child_id, metadata, parent_id)

Each OpMove::timestamp will be greater than the previous op in the returned list. Therefore, these operations can be successfully applied via ::apply_op() without timestamp collision.

Examples found in repository

examples/demo.rs (lines 57-62)

fn demo_concurrent_moves() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["root"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/a to /root/b
    let repl1_ops = vec![r1.opmove(ids["b"], "a", ids["a"])];

    // replica_2 "simultaneously" moves /root/a to /root/c
    let repl2_ops = vec![r2.opmove(ids["c"], "a", ids["a"])];

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/c/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    //    if r1.state.is_equal(&r2.state) {
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: cycle test from the paper
//
// Tests what happen when two peers independently perform operations that would
// introduce a cycle when combined.
//
// Upon applying eachother's ops, they must converge to a common location without
// any cycles.
fn demo_concurrent_moves_cycle() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["a"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/b to /root/a,  creating /root/a/b
    let repl1_ops = r1.opmoves(vec![(ids["a"], "b", ids["b"])]);

    // replica_2 "simultaneously" moves /root/a to /root/b, creating /root/b/a
    let repl2_ops = r2.opmoves(vec![(ids["b"], "a", ids["a"])]);

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/b/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: Walk a deep tree
//
// This demonstrates creation of a deep tree which we then walk in depth-first
// fashion.
//
// This particular tree contains 2^6-1 nodes and is up to 6 levels deep.
fn demo_walk_deep_tree() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [("root", new_id())].iter().cloned().collect();

    // Generate initial tree state.
    println!("generating ops...");
    let mut ops = vec![(0, "root", ids["root"])];
    mktree_ops(&mut ops, &mut r1, ids["root"], 2, 6); //  <-- max 6 levels deep.

    println!("applying ops...");
    let ops_len = ops.len();
    r1.apply_ops_byref(&r1.opmoves(ops));

    println!("walking tree...");
    r1.tree().walk(&ids["root"], |tree, node_id, depth| {
        if true {
            let meta = match tree.find(node_id) {
                Some(tn) => format!("{:?}", tn.metadata()),
                None => format!("{:?}", node_id),
            };
            println!("{:indent$}{}", "", meta, indent = depth);
        }
    });

    println!("\nnodes in tree: {}", ops_len);
}

/// Demonstrates log truncation
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
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);
}

/// Demonstrates moving items to a Trash node outside the nominal root and then
/// emptying the trash after the log is truncated.
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

pub fn id(&self) -> &A

Returns actor ID for this replica

Examples found in repository

examples/demo.rs (line 255)

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 time(&self) -> &Clock<A>

Returns the latest lamport time seen by this replica

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

Returns Tree State reference

Examples found in repository

examples/demo.rs (line 92)

fn demo_concurrent_moves() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["root"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/a to /root/b
    let repl1_ops = vec![r1.opmove(ids["b"], "a", ids["a"])];

    // replica_2 "simultaneously" moves /root/a to /root/c
    let repl2_ops = vec![r2.opmove(ids["c"], "a", ids["a"])];

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/c/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    //    if r1.state.is_equal(&r2.state) {
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: cycle test from the paper
//
// Tests what happen when two peers independently perform operations that would
// introduce a cycle when combined.
//
// Upon applying eachother's ops, they must converge to a common location without
// any cycles.
fn demo_concurrent_moves_cycle() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["a"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/b to /root/a,  creating /root/a/b
    let repl1_ops = r1.opmoves(vec![(ids["a"], "b", ids["b"])]);

    // replica_2 "simultaneously" moves /root/a to /root/b, creating /root/b/a
    let repl2_ops = r2.opmoves(vec![(ids["b"], "a", ids["a"])]);

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/b/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: Walk a deep tree
//
// This demonstrates creation of a deep tree which we then walk in depth-first
// fashion.
//
// This particular tree contains 2^6-1 nodes and is up to 6 levels deep.
fn demo_walk_deep_tree() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [("root", new_id())].iter().cloned().collect();

    // Generate initial tree state.
    println!("generating ops...");
    let mut ops = vec![(0, "root", ids["root"])];
    mktree_ops(&mut ops, &mut r1, ids["root"], 2, 6); //  <-- max 6 levels deep.

    println!("applying ops...");
    let ops_len = ops.len();
    r1.apply_ops_byref(&r1.opmoves(ops));

    println!("walking tree...");
    r1.tree().walk(&ids["root"], |tree, node_id, depth| {
        if true {
            let meta = match tree.find(node_id) {
                Some(tn) => format!("{:?}", tn.metadata()),
                None => format!("{:?}", node_id),
            };
            println!("{:indent$}{}", "", meta, indent = depth);
        }
    });

    println!("\nnodes in tree: {}", ops_len);
}

/// Demonstrates log truncation
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
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 tree(&self) -> &Tree<ID, TM>

Returns Tree reference

Examples found in repository

examples/demo.rs (line 68)

fn demo_concurrent_moves() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["root"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/a to /root/b
    let repl1_ops = vec![r1.opmove(ids["b"], "a", ids["a"])];

    // replica_2 "simultaneously" moves /root/a to /root/c
    let repl2_ops = vec![r2.opmove(ids["c"], "a", ids["a"])];

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/c/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    //    if r1.state.is_equal(&r2.state) {
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: cycle test from the paper
//
// Tests what happen when two peers independently perform operations that would
// introduce a cycle when combined.
//
// Upon applying eachother's ops, they must converge to a common location without
// any cycles.
fn demo_concurrent_moves_cycle() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["a"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/b to /root/a,  creating /root/a/b
    let repl1_ops = r1.opmoves(vec![(ids["a"], "b", ids["b"])]);

    // replica_2 "simultaneously" moves /root/a to /root/b, creating /root/b/a
    let repl2_ops = r2.opmoves(vec![(ids["b"], "a", ids["a"])]);

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/b/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: Walk a deep tree
//
// This demonstrates creation of a deep tree which we then walk in depth-first
// fashion.
//
// This particular tree contains 2^6-1 nodes and is up to 6 levels deep.
fn demo_walk_deep_tree() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [("root", new_id())].iter().cloned().collect();

    // Generate initial tree state.
    println!("generating ops...");
    let mut ops = vec![(0, "root", ids["root"])];
    mktree_ops(&mut ops, &mut r1, ids["root"], 2, 6); //  <-- max 6 levels deep.

    println!("applying ops...");
    let ops_len = ops.len();
    r1.apply_ops_byref(&r1.opmoves(ops));

    println!("walking tree...");
    r1.tree().walk(&ids["root"], |tree, node_id, depth| {
        if true {
            let meta = match tree.find(node_id) {
                Some(tn) => format!("{:?}", tn.metadata()),
                None => format!("{:?}", node_id),
            };
            println!("{:indent$}{}", "", meta, indent = depth);
        }
    });

    println!("\nnodes in tree: {}", ops_len);
}

/// Demonstrates log truncation
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
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);
}

/// Demonstrates moving items to a Trash node outside the nominal root and then
/// emptying the trash after the log is truncated.
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

fn print_help() {
    let buf = "
Usage: tree <demo>

<demo> can be any of:
  demo_concurrent_moves
  demo_concurrent_moves_cycle
  demo_truncate_log
  demo_walk_deep_tree
  demo_move_to_trash

";
    println!("{}", buf);
}

// Returns op tuples representing a depth-first tree,
// with 2 children for each parent.
fn mktree_ops(
    ops: &mut Vec<(TypeId, TypeMeta, TypeActor)>,
    r: &mut TreeReplica<TypeId, TypeMeta, TypeActor>,
    parent_id: u64,
    depth: usize,
    max_depth: usize,
) {
    if depth > max_depth {
        return;
    }

    for i in 0..2 {
        let name = if i == 0 { "a" } else { "b" };
        let child_id = new_id();
        ops.push((parent_id, name, child_id));
        mktree_ops(ops, r, child_id, depth + 1, max_depth);
    }
}

// applies each operation in ops to each replica in replicas.
fn apply_ops_to_replicas<ID, TM, A>(
    replicas: &mut [TreeReplica<ID, TM, A>],
    ops: &[OpMove<ID, TM, A>],
) where
    ID: TreeId,
    A: Actor + std::fmt::Debug,
    TM: TreeMeta,
{
    for r in replicas.iter_mut() {
        r.apply_ops_byref(ops);
    }
}

// note: in practice a UUID (at least 128 bits should be used)
fn new_id() -> TypeId {
    rand::random::<TypeId>()
}

// print a treenode, recursively
fn print_treenode<ID, TM>(tree: &Tree<ID, TM>, node_id: &ID, depth: usize, with_id: bool)
where
    ID: TreeId + std::fmt::Debug,
    TM: TreeMeta + std::fmt::Debug,
{
    let result = tree.find(node_id);
    let meta = match result {
        Some(tn) => format!("{:?}", tn.metadata()),
        None if depth == 0 => "forest".to_string(),
        None => {
            panic!("tree node {:?} not found", node_id);
        }
    };
    println!("{:indent$}{}", "", meta, indent = depth * 2);

    for c in tree.children(node_id) {
        print_treenode(tree, &c, depth + 1, with_id);
    }
}

// print a tree.
fn print_tree<ID, TM>(tree: &Tree<ID, TM>, root: &ID)
where
    ID: TreeId + std::fmt::Debug,
    TM: TreeMeta + std::fmt::Debug,
{
    print_treenode(tree, root, 0, false);
}

// print trees for two replicas
fn print_replica_trees<ID, TM, A>(
    repl1: &TreeReplica<ID, TM, A>,
    repl2: &TreeReplica<ID, TM, A>,
    root: &ID,
) where
    ID: TreeId + std::fmt::Debug,
    A: Actor + std::fmt::Debug,
    TM: TreeMeta + std::fmt::Debug,
{
    println!("\n--replica_1 --");
    print_tree(repl1.tree(), root);
    println!("\n--replica_2 --");
    print_tree(repl2.tree(), root);
    println!();
}

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.

Examples found in repository

examples/demo.rs (line 354)

fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

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

Applies single operation to State and updates our time clock

Also records latest timestamp for each replica if track_causally_stable_threshold flag is set.

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

Applies list of operations

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

Applies list of operations without taking ownership

Examples found in repository

examples/demo.rs (line 64)

fn demo_concurrent_moves() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["root"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/a to /root/b
    let repl1_ops = vec![r1.opmove(ids["b"], "a", ids["a"])];

    // replica_2 "simultaneously" moves /root/a to /root/c
    let repl2_ops = vec![r2.opmove(ids["c"], "a", ids["a"])];

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/c/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    //    if r1.state.is_equal(&r2.state) {
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: cycle test from the paper
//
// Tests what happen when two peers independently perform operations that would
// introduce a cycle when combined.
//
// Upon applying eachother's ops, they must converge to a common location without
// any cycles.
fn demo_concurrent_moves_cycle() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("root", new_id()),
        ("a", new_id()),
        ("b", new_id()),
        ("c", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Setup initial tree state.
    let ops = r1.opmoves(vec![
        (0, "root", ids["root"]),
        (ids["root"], "a", ids["a"]),
        (ids["root"], "b", ids["b"]),
        (ids["a"], "c", ids["c"]),
    ]);

    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("Initial tree state on both replicas");
    print_tree(r1.tree(), &ids["root"]);

    // replica_1 moves /root/b to /root/a,  creating /root/a/b
    let repl1_ops = r1.opmoves(vec![(ids["a"], "b", ids["b"])]);

    // replica_2 "simultaneously" moves /root/a to /root/b, creating /root/b/a
    let repl2_ops = r2.opmoves(vec![(ids["b"], "a", ids["a"])]);

    // replica_1 applies his op, then merges op from replica_2
    r1.apply_ops_byref(&repl1_ops);
    println!("\nreplica_1 tree after move");
    print_tree(r1.tree(), &ids["root"]);
    r1.apply_ops_byref(&repl2_ops);

    // replica_2 applies his op, then merges op from replica_1
    r2.apply_ops_byref(&repl2_ops);
    println!("\nreplica_2 tree after move");
    print_tree(r2.tree(), &ids["root"]);
    r2.apply_ops_byref(&repl1_ops);

    // expected result: state is the same on both replicas
    // and final path is /root/b/a because last-writer-wins
    // and replica_2's op has a later timestamp.
    if r1.state() == r2.state() {
        println!("\nreplica_1 state matches replica_2 state after each merges other's change.  conflict resolved!");
        print_replica_trees(&r1, &r2, &ids["root"]);
    } else {
        println!("\nwarning: replica_1 state does not match replica_2 state after merge");
        print_replica_trees(&r1, &r2, &ids["root"]);
        println!("-- replica_1 state --");
        println!("{:#?}", r1.state());
        println!("\n-- replica_2 state --");
        println!("{:#?}", r2.state());
    }
}

// Demo: Walk a deep tree
//
// This demonstrates creation of a deep tree which we then walk in depth-first
// fashion.
//
// This particular tree contains 2^6-1 nodes and is up to 6 levels deep.
fn demo_walk_deep_tree() {
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [("root", new_id())].iter().cloned().collect();

    // Generate initial tree state.
    println!("generating ops...");
    let mut ops = vec![(0, "root", ids["root"])];
    mktree_ops(&mut ops, &mut r1, ids["root"], 2, 6); //  <-- max 6 levels deep.

    println!("applying ops...");
    let ops_len = ops.len();
    r1.apply_ops_byref(&r1.opmoves(ops));

    println!("walking tree...");
    r1.tree().walk(&ids["root"], |tree, node_id, depth| {
        if true {
            let meta = match tree.find(node_id) {
                Some(tn) => format!("{:?}", tn.metadata()),
                None => format!("{:?}", node_id),
            };
            println!("{:indent$}{}", "", meta, indent = depth);
        }
    });

    println!("\nnodes in tree: {}", ops_len);
}

/// Demonstrates log truncation
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
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);
}

/// Demonstrates moving items to a Trash node outside the nominal root and then
/// emptying the trash after the log is truncated.
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

fn print_help() {
    let buf = "
Usage: tree <demo>

<demo> can be any of:
  demo_concurrent_moves
  demo_concurrent_moves_cycle
  demo_truncate_log
  demo_walk_deep_tree
  demo_move_to_trash

";
    println!("{}", buf);
}

// Returns op tuples representing a depth-first tree,
// with 2 children for each parent.
fn mktree_ops(
    ops: &mut Vec<(TypeId, TypeMeta, TypeActor)>,
    r: &mut TreeReplica<TypeId, TypeMeta, TypeActor>,
    parent_id: u64,
    depth: usize,
    max_depth: usize,
) {
    if depth > max_depth {
        return;
    }

    for i in 0..2 {
        let name = if i == 0 { "a" } else { "b" };
        let child_id = new_id();
        ops.push((parent_id, name, child_id));
        mktree_ops(ops, r, child_id, depth + 1, max_depth);
    }
}

// applies each operation in ops to each replica in replicas.
fn apply_ops_to_replicas<ID, TM, A>(
    replicas: &mut [TreeReplica<ID, TM, A>],
    ops: &[OpMove<ID, TM, A>],
) where
    ID: TreeId,
    A: Actor + std::fmt::Debug,
    TM: TreeMeta,
{
    for r in replicas.iter_mut() {
        r.apply_ops_byref(ops);
    }
}

pub fn apply_log_op(&mut self, log_op: LogOpMove<ID, TM, A>)

applies op from a log. useful for log replay.

pub fn apply_log_ops(&mut self, log_ops: Vec<LogOpMove<ID, TM, A>>)

applies ops from a log. useful for log replay.

pub fn causally_stable_threshold(&self) -> Option<&Clock<A>>

returns the causally stable threshold

Examples found in repository

examples/demo.rs (line 258)

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

/// Demonstrates moving items to a Trash node outside the nominal root and then
/// emptying the trash after the log is truncated.
///
/// This requires that causally stable threshold tracking is enabled in `TreeReplica`
fn demo_move_to_trash() {
    // pass true flag to enable causally stable threshold tracking
    let mut r1: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());
    let mut r2: TreeReplica<TypeId, TypeMeta, TypeActor> = TreeReplica::new(new_id());

    let ids: HashMap<&str, TypeId> = [
        ("forest", new_id()),
        ("trash", new_id()),
        ("root", new_id()),
        ("home", new_id()),
        ("bob", new_id()),
        ("project", new_id()),
    ]
    .iter()
    .cloned()
    .collect();

    // Generate initial tree state.
    //
    // - forest
    //   - trash
    //   - root
    //     - home
    //       - bob
    //         - project
    let mut ops = vec![
        (ids["forest"], "root", ids["root"]),
        (ids["forest"], "trash", ids["trash"]),
        (ids["root"], "home", ids["home"]),
        (ids["home"], "bob", ids["bob"]),
        (ids["bob"], "project", ids["project"]),
    ];

    // add some nodes under project
    mktree_ops(&mut ops, &mut r1, ids["project"], 2, 3);
    let opmoves = r1.opmoves(ops);
    r1.apply_ops_byref(&opmoves);
    r2.apply_ops_byref(&opmoves);

    println!("Initial tree");
    print_tree(r1.tree(), &ids["forest"]);

    // move project to trash
    let ops = vec![r1.opmove(ids["trash"], "project", ids["project"])];
    r1.apply_ops_byref(&ops);
    r2.apply_ops_byref(&ops);

    println!("\nAfter project moved to trash (deleted) on both replicas");
    print_tree(r1.tree(), &ids["forest"]);

    // Initially, trashed nodes must be retained because a concurrent move
    // operation may move them back out of the trash.
    //
    // Once the operation that moved a node to the trash is causally
    // stable, we know that no future operations will refer to this node,
    // and so the trashed node and its descendants can be discarded.
    //
    // note:  change r1.opmoves() to r2.opmoves() above to
    //        make the causally stable threshold less than the trash operation
    //        timestamp, which will cause this test to fail, ie hit the
    //        "trash should not be emptied" condition.
    let result = r2.causally_stable_threshold();
    match result {
        Some(cst) if cst < ops[0].timestamp() => {
            println!(
                "\ncausally stable threshold:\n{:#?}\n\ntrash operation:\n{:#?}",
                cst,
                ops[0].timestamp()
            );
            panic!("!error: causally stable threshold is less than trash operation timestamp");
        }
        None => panic!("!error: causally stable threshold not found"),
        _ => {}
    }

    // empty trash
    r1.tree_mut().rm_subtree(&ids["trash"], false);
    println!("\nDelete op is now causally stable, so we can empty trash:");
    print_tree(r1.tree(), &ids["forest"]);
}

pub fn truncate_log(&mut self) -> bool

truncates log

Examples found in repository

examples/demo.rs (line 261)

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

Trait Implementations

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

impl<'de, ID, TM, A> Deserialize<'de> for TreeReplica<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: PartialEq + TreeId, TM: PartialEq + TreeMeta, A: PartialEq + Actor> PartialEq for TreeReplica<ID, TM, A>

fn eq(&self, other: &TreeReplica<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 TreeReplica<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 TreeReplica<ID, TM, A>

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