Struct OpMove 

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

Implements OpMove, the only way to manipulate tree data.

OpMove are applied via State::apply_op() or at a higher level via TreeReplica::apply_op()

From the paper[1]:

We allow the tree to be updated in three ways: by creating a new child of any parent node, by deleting a node, or by moving a node to be a child of a new parent. However all three types of update can be represented by a move operation. To create a node, we generate a fresh ID for that node, and issue an operation to move this new ID to be created. We also designate as “trash” some node ID that does not exist in the tree; then we can delete a node by moving it to be a child of the trash.

Thus, we define one kind of operation: Move t p m c. A move operation is a 4-tuple consisting of a timestamp t of type ’t, a parent node ID p of type ’n, a metadata field m of type ’m, and a child node ID c of type ’n. Here, ’t, ’n, and ’m are type variables that can be replaced with arbitrary types; we only require that node identifiers ’n are globally unique (eg UUIDs); timestamps ’t need to be globally unique and totally ordered (eg Lamport timestamps [11]).

The meaning of an operation Move t p m c is that at time t, the node with ID c is moved to be a child of the parent node with ID p. The operation does not specify the old location of c; the algorithm simply removes c from wherever it is currently located in the tree, and moves it to p. If c does not currently exist in the tree, it is created as a child of p.

The metadata field m in a move operation allows additional information to be associated with the parent-child relationship of p and c. For example, in a filesystem, the parent and child are the inodes of a directory and a file within it respectively, and the metadata contains the filename of the child. Thus, a file with inode c can be renamed by performing a Move t p m c, where the new parent directory p is the inode of the existing parent (unchanged), but the metadata m contains the new filename.

When users want to make changes to the tree on their local replica they generate new Move t p m c operations for these changes, and apply these operations using the algorithm described…

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

Implementations

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

pub fn new( timestamp: Clock<A>, parent_id: ID, metadata: TM, child_id: ID, ) -> Self

create a new OpMove instance

pub fn timestamp(&self) -> &Clock<A>

returns timestamp reference

Examples found in repository

examples/demo.rs (line 341)

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 parent_id(&self) -> &ID

returns parent_id reference

pub fn metadata(&self) -> &TM

returns metadata reference

pub fn child_id(&self) -> &ID

returns child_id reference

Trait Implementations

impl<ID: TreeId + Arbitrary, A: Actor + Arbitrary, TM: TreeMeta + Arbitrary> Arbitrary for OpMove<ID, TM, A>

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

generates an arbitrary (random) OpMove

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

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

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

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

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<ID: TreeId, A: Actor, TM: TreeMeta> From<LogOpMove<ID, TM, A>> for OpMove<ID, TM, A>

fn from(l: LogOpMove<ID, TM, A>) -> Self

creates OpMove from a LogOpMove

impl<ID: Hash + TreeId, TM: Hash + TreeMeta, A: Hash + Actor> Hash for OpMove<ID, TM, A>

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

Feeds this value into the given Hasher.

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

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

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

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

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