CRDTree

The local replica state.

Not two replicas should have the same id across a network, a server should be used to assign unique numeric ids to each replica.

The timestamp for the replica is a vector clock, encoded as an integer, consisting in the id of the replica taking the first bits and the number of the last operation taking the last 32 bits.

The path of a node in the tree is represented as a List Int.

Init

type CRDTree a

A Replicated Tree, see int.

init : Int -> CRDTree a

Build a CRDTree providing the replica id.

tree : CRDTree String
tree = init 1

Operations

type Error a

= Error (Operation a)

Failure to apply an operation

add : a -> CRDTree a -> Result (Error a) (CRDTree a)

Add a node after tree cursor, the cursor is set at the added node path.

init 1
  |> add "a"
  |> Result.andThen (add "b")
  |> Result.andThen (add "c")

addAfter : List Int -> a -> CRDTree a -> Result (Error a) (CRDTree a)

Add a node after another node at given path, the cursor is set at the added node path.

init 1
  |> add "a"
  |> Result.andThen (add "b")
  |> Result.andThen (addAfter [1] "c")
-- node with value "c" is inserted between nodes "a" and "b"

addBranch : a -> CRDTree a -> Result (Error a) (CRDTree a)

Add a branch after tree cursor, subsequent additions are added to the branch.

init 1
  |> addBranch "a"
  |> Result.andThen (add "a,b")
  |> Result.andThen (add "a,c")

batch :

List (CRDTree a -> Result (Error a) (CRDTree a))

-> CRDTree a

-> Result (Error a) (CRDTree a)

Apply a list of operations

init 1 |> batch [ add "a", add "b", add "c" ]

delete : List Int -> CRDTree a -> Result (Error a) (CRDTree a)

Mark a node at a path as deleted.

init 1
  |> batch [ add "a", add "b" ]
  |> Result.andThen (\tree -> delete (cursor tree) tree)

Nodes are not actually deleted but marked and their children discarded.

apply : Operation a -> CRDTree a -> Result (Error a) (CRDTree a)

Apply a remote operation

treeA : CRDTree String
treeA =
  let
      tree = init 1
  in
  tree
    |> batch [ add "a", add "b", add "c" ]
    |> Result.withDefault tree


operation : Operation String
operation =
  lastOperation treeA


treeB : CRDTree String
treeB =
  let
      tree = init 1
  in
  tree
    |> apply operation
    |> Result.withDefault tree


(root treeA) == (root treeB)
(operations treeA) == (operations treeB)
(path treeA) /= (path treeB)
(timestamp treeA) /= (timestamp treeB)

operationsSince : Int -> CRDTree a -> Operation a

Return a batch of operations after a known timestamp

treeA : CRDTree String
treeA =
  let
      tree = init 1
  in
  tree
    |> batch [ add "a", add "b" ]
    |> Result.withDefault tree


(List.length (Operation.toList <| operationsSince 0 treeA)) == 2
(List.length (Operation.toList <| operationsSince 1 treeA)) == 2
(List.length (Operation.toList <| operationsSince 2 treeA)) == 1


(List.length (Operation.toList <| operationsSince 5 treeA)) == 0

lastOperation : CRDTree a -> Operation a

Return the last successfully applied operation or batch or if operation was not succesfull an empty batch.

  import Operation exposing (Operation(..))


  -- success
  init 1
    |> batch [ add "a", add "b", add "c" ]
    |> Result.map (\tree ->
         (lastOperation tree) /= Batch [])


  -- failure
  init 1
    |> delete [1,2,3]
    |> Result.map (\tree ->
        (lastOperation tree) == Batch [])

Tree

id : CRDTree a -> Int

The local replica id

timestamp : CRDTree a -> Int

The local replica timestamp

root : CRDTree a -> Node a

Root node of the CRDTree

get : List Int -> CRDTree a -> Maybe (Node a)

Get a value at path

treeA : CRDTree String
treeA =
  let
      tree = init 1
  in
  tree
    |> batch [ addBranch "a", addBranch "b", add "c" ]
    |> Result.withDefault tree


(get [1] treeA) == (Just (Node.init "a" [1]))
(get [1, 2] treeA) == (Just (Node.init "b" [1,2]))
(get [1, 2, 3] treeA) == (Just (Node.init "c" [1, 2, 3]))
(get [4] treeA) == Nothing

getValue : List Int -> CRDTree a -> Maybe a

Get a value at path

treeA : CRDTree String
treeA =
  let
      tree = init 1
  in
  tree
    |> batch [ addBranch "a", addBranch "b", add "c" ]
    |> Result.withDefault tree


(get [1] treeA) == (Just "a")
(get [1, 2] treeA) == (Just "b")
(get [1, 2, 3] treeA) == (Just "c")
(get [4] treeA) == Nothing

cursor : CRDTree a -> List Int

Return the tree cursor

treeA : CRDTree String
treeA =
  let
      tree = init 1
  in
  tree
    |> batch [ add "a", add "b", add "c" ]
    |> Result.withDefault tree


(cursor treeA) == [3]




treeB : CRDTree String
treeB =
  let
      tree = init 1
  in
  tree
    |> batch [ addBranch "a", addBranch "b" ]
    |> Result.withDefault tree


(cursor treeB) == [1, 2, 0]

moveCursorUp : CRDTree a -> CRDTree a

Move the tree cursor one level up

treeA : CRDTree String
treeA =
  let
      tree = init 1
  in
  tree
    |> batch [ addBranch "a", addBranch "b", add "c" ]
    |> Result.withDefault tree


(cursor treeA) == [1, 2, 3]
(cursor (moveCursorUp treeA)) == [1, 2]

Replicas

lastReplicaTimestamp : Int -> CRDTree a -> Int

Last know timestamp for a replica

maca/crdt-replicated-tree/5.0.0

CRDTree

Init

Operations

Tree

Replicas

Modules