Opaque type representing a Replicated Tree, to build see int.

Build a CRDTree

tree : CRDTree String
tree = init { id = 1, maxReplicas = 1024 }

id for this replica, not two replicas can have the same id. To ensure this, it shuld be assigned by a server.

maxReplicas maximum number of possible replicas, this value has to be assigned to generate unique timestamps.

Represents the failure to apply an operation

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

init { id = 1, maxReplicas = 4 }
  |> add "a"
  |> Result.andThen (add "b")
  |> Result.andThen (add "c")

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

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

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

init { id = 1, maxReplicas = 4 }
  |> addBranch "a"
  |> Result.andThen (add "a,b")
  |> Result.andThen (add "a,c")

Apply a list of operations

init { id = 1, maxReplicas = 4 }
  |> batch [ add "a", add "b", add "c" ]

Mark a node at a path as deleted.

init { id = 1, maxReplicas = 4 }
  |> batch [ add "a", add "b" ]
  |> Result.andThen (\tree -> delete (cursor tree) tree)

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

Apply a remote operation

treeA : CRDTree String
treeA =
  let
      tree =
        init { id = 1, maxReplicas = 2 }
  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 { id = 1, maxReplicas = 2 }
  in
  tree
    |> apply operation
    |> Result.withDefault tree


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

Return a list of operations after a known timestamp

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


(List.length (operationsSince 0 treeA)) == 2
(List.length (operationsSince 2 treeA)) == 2
(List.length (operationsSince 4 treeA)) == 1


-- 1, 3 are not known timestamps, since the
-- logic clock increment depends on `maxReplicas`
(List.length (operationsSince 1 treeA)) == 0
(List.length (operationsSince 3 treeA)) == 0

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

  import Operation exposing (Operation(..))


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


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

The local replica id

The local replica timestamp

Root node of the CRDTree

Get a value at path

treeA : CRDTree String
treeA =
  let
      tree =
        init { id = 1, maxReplicas = 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

Get a value at path

treeA : CRDTree String
treeA =
  let
      tree =
        init { id = 1, maxReplicas = 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

Return the tree cursor

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


(cursor treeA) == [3]




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


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

Move the tree cursor one level up

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


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

Last know timestamp for a replica