Struct TreeNode 

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

TreeNode is a node that is stored in a Tree.

Logically, each TreeNode consists of a triple (parent_id, metadata, child_id). However, in this implementation, the child_id is stored as the key in Tree::triples HashMap<ID, TreeNode>

Implementations

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

pub fn new(parent_id: ID, metadata: TM) -> Self

creates a new TreeNode instance

pub fn parent_id(&self) -> &ID

returns parent_id reference

pub fn metadata(&self) -> &TM

returns metadata reference

Examples found in repository

examples/demo.rs (line 198)

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

Trait Implementations

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

fn clone(&self) -> TreeNode<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 TreeNode<ID, TM>

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

Formats the value using the given formatter.

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

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

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