Sequence

A CRDT for sequential data (eg. lists of characters aka. text)

Implementation took inspiration from from Nedelec et al. "LSEQ: an adaptive structure for sequences in distributed collaborative editing" (2013).

Definition

type Sequence a

The data type itself. Takes a user-defined type as its value type.

type Path

The unique identifier of a Entry's position in the sequence. It consists of a list of positions, one for each layer in the data structure.

Eg. given this data structure:

[a|b|c|d]
  |
  [x|y]

'a' has path [0]
'c' has path [2]
'x' has path [1,0]

type Entry a

= Single String (Value a)

| Concurrent (MVR a)

An entry in the sequence might be a single value (just one user applied an operation on it) or a multi-value registry (MVR) in case multiple users a applied operation at this path.

type Value a

= Value a

| Tomb (TombValue a)

The actual value. After applying an Insert operation it is Value a, after a Remove operation it is a Tomb (TombValue a). So storage of removed values never gets freed.

type TombValue a

= TombValue a

| TombUnknown

If a remove operation is applied at a path which has a value, it's turned into Tomb (TombValue a). If the operation is applied on a free path it becomes TombUnknown. If an insert operation is applied after this, it's turned into TombValue a finally. This way it does not matter in which order insert and remove operation are applied.

type MVR a

A multi-value registry is a dictionary of user identifiers and Values. Get its contents with mvrToRecord.

type Operation a

= Insert a

| Remove

All data manipulation happens through Operations. It either is an Insert a or Remove.

type alias Op b =

{ origin : String

, target : String

, path : Path

, op : Operation b

}

The complete self-contained op(eration). origin is the identifier for the creating user/instance. If the Entry at path already contains a MVR apply the operation at target's value.

Operations

alloc : Path -> Path -> Path

Allocate a path given it's lower and upper bounds (non-inclusive).

createInsert : String -> Path -> a -> Op a

Create an insert operation. Pass it the user identifier, a path and the value to insert.

createRemove : String -> String -> Path -> Op a

Create a remove operation. Pass it the removing user's identifier, the user identifier of the removed value (ie. to target it in a MVR) and the path.

apply : List (Op a) -> Sequence a -> ( Sequence a, List (Op a) )

Apply multiple ops at once to a sequence. Returns the updated sequence and list of successful operations (which actually changed something).

Sequence handling

empty : Sequence a

An empty sequence.

get : Path -> Sequence a -> Maybe (Entry a)

Lookup an entry at the given path.

first : Sequence a -> Maybe ( Path, Entry a )

Return the first entry of the sequence and its path. If the sequence is empty returns Nothing.

last : Sequence a -> Maybe ( Path, Entry a )

Return the last entry of the sequence and its path. If the sequence is empty returns Nothing.

after : Path -> Sequence a -> Maybe ( Path, Entry a )

Return the entry and its path after the given path in the sequence. Returns Nothing if there is none.

before : Path -> Sequence a -> Maybe ( Path, Entry a )

Return the entry and its path before the given path in the sequence. Returns Nothing if there is none.

foldl : (Path -> Entry a -> b -> b) -> b -> Sequence a -> b

Fold a sequence from the left.

foldr : (Path -> Entry a -> b -> b) -> b -> Sequence a -> b

Fold a sequence from the right.

MVR handling

mvrToRecord :

MVR a

-> { first : ( String, Value a )

, second : ( String, Value a )

, more : List ( String, Value a )

}

Inspect an MVR by turning it into a record of the first, the second and a list of more entries.

mvrToList : MVR a -> List ( String, Value a )

Convenience function to turn an MVR into a list of entries.

mvrFilterValues : MVR a -> List ( String, a )

Filter MVR for Values.

mvrFoldl : (String -> Value a -> b -> b) -> b -> MVR a -> b

Fold an MVR from left.

mvrFoldr : (String -> Value a -> b -> b) -> b -> MVR a -> b

Fold an MVR from right.

mvrGet : String -> MVR a -> Maybe (Value a)

Get a value from an MVR given the origin.

mvrSize : MVR a -> Int

Get the size of an MVR.

Decoders

decodeOp : Decoder a -> Decoder (Op a)

Decode an Op.

encodeOp : (a -> Value) -> Op a -> Value

Encode an Op given a value specific encoder.

Paths

minPath : Path

The lowest path possible

maxPath : Path

The greatest path possible

path : Int -> List Int -> Path

Create a path (ie. a non-empty list) given its head and tail.

comparePath : Path -> Path -> Order

Compare Paths

pathToString : Path -> String

Turn a path into a string.

Modules

Sequence

brightdb/sequence/1.2.0