Struct Tree 

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

Implements Tree, a set of triples representing current tree structure.

Normally this Tree struct should not be instantiated directly. Instead instantiate State (lower-level) or TreeReplica (higher-level) and invoke operations on them.

From the paper[1]:

We can represent the tree as a set of (parent, meta, child) triples, denoted in Isabelle/HOL as (’n × ’m × ’n) set. When we have (p, m, c) ∈ tree, that means c is a child of p in the tree, with associated metadata m. Given a tree, we can construct a new tree’ in which the child c is moved to a new parent p, with associated metadata m, as follows:

tree’ = {(p’, m’, c’) ∈ tree. c’ != c} ∪ {(p, m, c)}

That is, we remove any existing parent-child relationship for c from the set tree, and then add {(p, m, c)} to represent the new parent-child relationship.

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

Implementations

impl<ID: TreeId, TM: TreeMeta> Tree<ID, TM>

pub fn new() -> Self

create a new Tree instance

pub fn rm_child(&mut self, child_id: &ID)

helper for removing a triple based on child_id

pub fn rm_subtree(&mut self, parent_id: &ID, include_parent: bool)

removes a subtree. useful for emptying trash. not used by crdt algo.

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 add_node(&mut self, child_id: ID, tt: TreeNode<ID, TM>)

adds a node to the tree

pub fn find(&self, child_id: &ID) -> Option<&TreeNode<ID, TM>>

returns matching node, or None.

Examples found in repository

examples/demo.rs (line 197)

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

pub fn children(&self, parent_id: &ID) -> Vec<ID>

returns children (IDs) of a given parent node. useful for walking tree. not used by crdt algo.

Examples found in repository

examples/demo.rs (line 430)

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

pub fn walk<F>(&self, parent_id: &ID, f: F)

where F: FnMut(&Self, &ID, usize),

walks tree and calls FnMut f for each node. not used by crdt algo.

walk uses a non-recursive algorithm, so calling it on a deep tree will not cause stack overflow.

Examples found in repository

examples/demo.rs (lines 195-203)

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

pub fn is_ancestor(&self, child_id: &ID, ancestor_id: &ID) -> bool

returns true if ancestor_id is an ancestor of child_id in tree.

parent | child
--------------
1        2
1        3
3        5
2        6
6        8

                 1
              2     3
            6         5
          8

is 2 ancestor of 8?  yes.
is 2 ancestor of 5?   no.

pub fn num_nodes(&self) -> usize

Total number of nodes (triples) in the tree

Trait Implementations

impl<ID: Clone + TreeId, TM: Clone + TreeMeta> Clone for Tree<ID, TM>

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

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> Debug for Tree<ID, TM>

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

Formats the value using the given formatter.

impl<ID: Default + TreeId, TM: Default + TreeMeta> Default for Tree<ID, TM>

fn default() -> Tree<ID, TM>

Returns the “default value” for a type.

impl<'de, ID, TM> Deserialize<'de> for Tree<ID, TM>

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

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<ID: TreeId + Debug, TM: TreeMeta + Debug> Display for Tree<ID, TM>

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

Formats the value using the given formatter.

impl<ID: TreeId, TM: TreeMeta> IntoIterator for Tree<ID, TM>

Implement IntoIterator for Tree. This is useful for walking all Nodes in 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> PartialEq for Tree<ID, TM>

fn eq(&self, other: &Tree<ID, TM>) -> 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> Serialize for Tree<ID, TM>

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

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> Eq for Tree<ID, TM>

impl<ID: TreeId, TM: TreeMeta> StructuralPartialEq for Tree<ID, TM>