Data.Mergeful.Collection

A way to synchronise a single item with safe merge conflicts.

The setup is as follows:

• A central server is set up to synchronise with
• Each client synchronises with the central server, but never with eachother

A client should operate as follows:

The client starts with an initialClientStore.

• The client produces a SyncRequest with makeSyncRequest.
• The client sends that request to the central server and gets a SyncResponse.
• The client then updates its local store with mergeSyncResponseIgnoreProblems.

The central server should operate as follows:

The server starts with an initialServerStore.

• The server accepts a SyncRequest.
• The server performs operations according to the functionality of processServerSync.
• The server respons with a SyncResponse.

WARNING: This whole approach can break down if a server resets its server times or if a client syncs with two different servers using the same server times.

Documentation

initialClientStore :: ClientStore i a

A client store to start with.

This store contains no items.

clientStoreSize :: ClientStore i a -> Word

The number of items in a client store

This does not count the deleted items, so that they really look deleted..

clientStoreClientIdSet :: ClientStore i a -> Set ClientId

The set of client ids.

These are only the client ids of the added items that have not been synced yet.

clientStoreUndeletedSyncIdSet :: Ord i => ClientStore i a -> Set i

The set of server ids.

This does not include the ids of items that have been marked as deleted.

clientStoreSyncIdSet :: Ord i => ClientStore i a -> Set i

The set of server ids.

This includes the ids of items that have been marked as deleted.

clientStoreItems :: Ord i => ClientStore i a -> Map (Either ClientId i) a

The set of items in the client store

This map does not include items that have been marked as deleted.

addItemToClientStore :: a -> ClientStore i a -> ClientStore i a

Add an item to a client store as an added item.

This will take care of the uniqueness constraint of the ClientIds in the map.

markItemDeletedInClientStore :: Ord i => i -> ClientStore i a -> ClientStore i a

Mark an item deleted in a client store.

This function will not delete the item, but mark it as deleted instead.

changeItemInClientStore :: Ord i => i -> a -> ClientStore i a -> ClientStore i a

Replace the given item with a new value.

This function will correctly mark the item as changed, if it exist.

It will not add an item to the store with the given id, because the server may not have been the origin of that id.

deleteItemFromClientStore :: ClientId -> ClientStore i a -> ClientStore i a

Delete an unsynced item from a client store.

This function will immediately delete the item, because it has never been synced.

initialSyncRequest :: SyncRequest i a

An intial SyncRequest to start with.

It just asks the server to send over whatever it knows.

makeSyncRequest :: ClientStore i a -> SyncRequest i a

Produce an SyncRequest from a ClientStore.

Send this to the server for synchronisation.

mergeSyncResponseIgnoreProblems :: Ord i => ClientStore i a -> SyncResponse i a -> ClientStore i a

Merge an SyncResponse into the current ClientStore.

This function ignores any problems that may occur. In the case of a conclict, it will just not update the client item. The next sync request will then produce a conflict again.

Pro: No data will be lost

Con: Clients will diverge when conflicts occur.

mergeSyncResponseFromServer :: Ord i => ClientStore i a -> SyncResponse i a -> ClientStore i a

Merge an SyncResponse into the current ClientStore by taking whatever the server gave the client.

Pro: Clients will converge on the same value.

Con: Conflicting updates will be lost.

Custom merging

data ItemMergeStrategy a

A strategy to merge conflicts for item synchronisation

Constructors

ItemMergeStrategy

Fields

• itemMergeStrategyMergeChangeConflict :: a -> Timed a -> Timed a

  How to merge modification conflicts

• itemMergeStrategyMergeClientDeletedConflict :: Timed a -> Maybe (Timed a)

  How to merge conflicts where the client deleted an item that the server modified

• itemMergeStrategyMergeServerDeletedConflict :: a -> Maybe a

  How to merge conflicts where the server deleted an item that the client modified

Instances

Generic (ItemMergeStrategy a)

Defined in Data.Mergeful.Item

Associated Types

type Rep (ItemMergeStrategy a) :: Type -> Type

Methods

from :: ItemMergeStrategy a -> Rep (ItemMergeStrategy a) x

to :: Rep (ItemMergeStrategy a) x -> ItemMergeStrategy a

type Rep (ItemMergeStrategy a)

Defined in Data.Mergeful.Item

type Rep (ItemMergeStrategy a) = D1 (MetaData "ItemMergeStrategy" "Data.Mergeful.Item" "mergeful-0.1.0.0-ABXYstvyIa5Kq6M8t1wQCW" False) (C1 (MetaCons "ItemMergeStrategy" PrefixI True) (S1 (MetaSel (Just "itemMergeStrategyMergeChangeConflict") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (a -> Timed a -> Timed a)) :*: (S1 (MetaSel (Just "itemMergeStrategyMergeClientDeletedConflict") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Timed a -> Maybe (Timed a))) :*: S1 (MetaSel (Just "itemMergeStrategyMergeServerDeletedConflict") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (a -> Maybe a)))))

mergeSyncResponseUsingStrategy :: Ord i => ItemMergeStrategy a -> ClientStore i a -> SyncResponse i a -> ClientStore i a

Merge an SyncResponse into the current ClientStore with the given merge strategy.

In order for clients to converge on the same collection correctly, this function must be:

• Associative
• Idempotent
• The same on all clients

This function ignores mismatches.

Server side

initialServerStore :: ServerStore i a

A server store to start with

This store contains no items.

processServerSync

Arguments

:: (Ord i, Monad m)

=> m i

The action that is guaranteed to generate unique identifiers

-> ServerStore i a

-> SyncRequest i a

-> m (SyncResponse i a, ServerStore i a)

Serve an SyncRequest using the current ServerStore, producing an SyncResponse and a new ServerStore.

Types, for reference

data ClientStore i a

Constructors

ClientStore

Fields

• clientStoreAddedItems :: Map ClientId a

  These items are new locally but have not been synced to the server yet.

• clientStoreSyncedItems :: Map i (Timed a)

  These items have been synced at their respective ServerTimes.

• clientStoreSyncedButChangedItems :: Map i (Timed a)

  These items have been synced at their respective ServerTimes but modified locally since then.

• clientStoreDeletedItems :: Map i ServerTime

  These items have been deleted locally after they were synced but the server has not been notified of that yet.

Instances

(Eq a, Eq i) => Eq (ClientStore i a)

Defined in Data.Mergeful.Collection

Methods

(==) :: ClientStore i a -> ClientStore i a -> Bool

(/=) :: ClientStore i a -> ClientStore i a -> Bool

(Show a, Show i) => Show (ClientStore i a)

Defined in Data.Mergeful.Collection

Methods

showsPrec :: Int -> ClientStore i a -> ShowS

show :: ClientStore i a -> String

showList :: [ClientStore i a] -> ShowS

Generic (ClientStore i a)

Defined in Data.Mergeful.Collection

Associated Types

type Rep (ClientStore i a) :: Type -> Type

Methods

from :: ClientStore i a -> Rep (ClientStore i a) x

to :: Rep (ClientStore i a) x -> ClientStore i a

(ToJSONKey i, ToJSON a) => ToJSON (ClientStore i a)

Defined in Data.Mergeful.Collection

Methods

toJSON :: ClientStore i a -> Value

toEncoding :: ClientStore i a -> Encoding

toJSONList :: [ClientStore i a] -> Value

toEncodingList :: [ClientStore i a] -> Encoding

(Ord i, FromJSONKey i, FromJSON a) => FromJSON (ClientStore i a)

Defined in Data.Mergeful.Collection

Methods

parseJSON :: Value -> Parser (ClientStore i a)

parseJSONList :: Value -> Parser [ClientStore i a]

(Validity i, Show i, Ord i, Validity a) => Validity (ClientStore i a)

Defined in Data.Mergeful.Collection

Methods

validate :: ClientStore i a -> Validation

type Rep (ClientStore i a)

Defined in Data.Mergeful.Collection

type Rep (ClientStore i a) = D1 (MetaData "ClientStore" "Data.Mergeful.Collection" "mergeful-0.1.0.0-ABXYstvyIa5Kq6M8t1wQCW" False) (C1 (MetaCons "ClientStore" PrefixI True) ((S1 (MetaSel (Just "clientStoreAddedItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map ClientId a)) :*: S1 (MetaSel (Just "clientStoreSyncedItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a)))) :*: (S1 (MetaSel (Just "clientStoreSyncedButChangedItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a))) :*: S1 (MetaSel (Just "clientStoreDeletedItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i ServerTime)))))

data SyncRequest i a

Constructors

SyncRequest

Fields

• syncRequestNewItems :: Map ClientId a

  These items are new locally but have not been synced to the server yet.

• syncRequestKnownItems :: Map i ServerTime

  These items have been synced at their respective ServerTimes.

• syncRequestKnownButChangedItems :: Map i (Timed a)

  These items have been synced at their respective ServerTimes but modified locally since then.

• syncRequestDeletedItems :: Map i ServerTime

  These items have been deleted locally after they were synced but the server has not been notified of that yet.

Instances

(Eq a, Eq i) => Eq (SyncRequest i a)

Defined in Data.Mergeful.Collection

Methods

(==) :: SyncRequest i a -> SyncRequest i a -> Bool

(/=) :: SyncRequest i a -> SyncRequest i a -> Bool

(Show a, Show i) => Show (SyncRequest i a)

Defined in Data.Mergeful.Collection

Methods

showsPrec :: Int -> SyncRequest i a -> ShowS

show :: SyncRequest i a -> String

showList :: [SyncRequest i a] -> ShowS

Generic (SyncRequest i a)

Defined in Data.Mergeful.Collection

Associated Types

type Rep (SyncRequest i a) :: Type -> Type

Methods

from :: SyncRequest i a -> Rep (SyncRequest i a) x

to :: Rep (SyncRequest i a) x -> SyncRequest i a

(ToJSONKey i, ToJSON a) => ToJSON (SyncRequest i a)

Defined in Data.Mergeful.Collection

Methods

toJSON :: SyncRequest i a -> Value

toEncoding :: SyncRequest i a -> Encoding

toJSONList :: [SyncRequest i a] -> Value

toEncodingList :: [SyncRequest i a] -> Encoding

(Ord i, FromJSONKey i, FromJSON a) => FromJSON (SyncRequest i a)

Defined in Data.Mergeful.Collection

Methods

parseJSON :: Value -> Parser (SyncRequest i a)

parseJSONList :: Value -> Parser [SyncRequest i a]

(Validity i, Show i, Ord i, Validity a) => Validity (SyncRequest i a)

Defined in Data.Mergeful.Collection

Methods

validate :: SyncRequest i a -> Validation

type Rep (SyncRequest i a)

Defined in Data.Mergeful.Collection

type Rep (SyncRequest i a) = D1 (MetaData "SyncRequest" "Data.Mergeful.Collection" "mergeful-0.1.0.0-ABXYstvyIa5Kq6M8t1wQCW" False) (C1 (MetaCons "SyncRequest" PrefixI True) ((S1 (MetaSel (Just "syncRequestNewItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map ClientId a)) :*: S1 (MetaSel (Just "syncRequestKnownItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i ServerTime))) :*: (S1 (MetaSel (Just "syncRequestKnownButChangedItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a))) :*: S1 (MetaSel (Just "syncRequestDeletedItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i ServerTime)))))

data SyncResponse i a

Constructors

SyncResponse

Fields

• syncResponseClientAdded :: Map ClientId (i, ServerTime)

  The client added these items and server has succesfully been made aware of that.

  The client needs to update their server times

• syncResponseClientChanged :: Map i ServerTime

  The client changed these items and server has succesfully been made aware of that.

  The client needs to update their server times

• syncResponseClientDeleted :: Set i

  The client deleted these items and server has succesfully been made aware of that.

  The client can delete them from its deleted items

• syncResponseServerAdded :: Map i (Timed a)

  These items have been added on the server side

  The client should add them too.

• syncResponseServerChanged :: Map i (Timed a)

  These items have been modified on the server side.

  The client should modify them too.

• syncResponseServerDeleted :: Set i

  These items were deleted on the server side

  The client should delete them too

• syncResponseConflicts :: Map i (Timed a)

  These are conflicts where the server and the client both have an item, but it is different.

  The server kept its part of each, the client can either take whatever the server gave them or deal with the conflicts somehow, and then try to re-sync.

• syncResponseConflictsClientDeleted :: Map i (Timed a)

  These are conflicts where the server has an item but the client does not.

  The server kept its item, the client can either take whatever the server gave them or deal with the conflicts somehow, and then try to re-sync.

• syncResponseConflictsServerDeleted :: Set i

  These are conflicts where the server has no item but the client has a modified item.

  The server left its item deleted, the client can either delete its items too or deal with the conflicts somehow, and then try to re-sync.

Instances

(Eq i, Eq a) => Eq (SyncResponse i a)

Defined in Data.Mergeful.Collection

Methods

(==) :: SyncResponse i a -> SyncResponse i a -> Bool

(/=) :: SyncResponse i a -> SyncResponse i a -> Bool

(Show i, Show a) => Show (SyncResponse i a)

Defined in Data.Mergeful.Collection

Methods

showsPrec :: Int -> SyncResponse i a -> ShowS

show :: SyncResponse i a -> String

showList :: [SyncResponse i a] -> ShowS

Generic (SyncResponse i a)

Defined in Data.Mergeful.Collection

Associated Types

type Rep (SyncResponse i a) :: Type -> Type

Methods

from :: SyncResponse i a -> Rep (SyncResponse i a) x

to :: Rep (SyncResponse i a) x -> SyncResponse i a

(ToJSON i, ToJSONKey i, ToJSON a) => ToJSON (SyncResponse i a)

Defined in Data.Mergeful.Collection

Methods

toJSON :: SyncResponse i a -> Value

toEncoding :: SyncResponse i a -> Encoding

toJSONList :: [SyncResponse i a] -> Value

toEncodingList :: [SyncResponse i a] -> Encoding

(Ord i, FromJSON i, FromJSONKey i, FromJSON a) => FromJSON (SyncResponse i a)

Defined in Data.Mergeful.Collection

Methods

parseJSON :: Value -> Parser (SyncResponse i a)

parseJSONList :: Value -> Parser [SyncResponse i a]

(Validity i, Show i, Ord i, Validity a) => Validity (SyncResponse i a)

Defined in Data.Mergeful.Collection

Methods

validate :: SyncResponse i a -> Validation

type Rep (SyncResponse i a)

Defined in Data.Mergeful.Collection

type Rep (SyncResponse i a) = D1 (MetaData "SyncResponse" "Data.Mergeful.Collection" "mergeful-0.1.0.0-ABXYstvyIa5Kq6M8t1wQCW" False) (C1 (MetaCons "SyncResponse" PrefixI True) (((S1 (MetaSel (Just "syncResponseClientAdded") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map ClientId (i, ServerTime))) :*: S1 (MetaSel (Just "syncResponseClientChanged") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i ServerTime))) :*: (S1 (MetaSel (Just "syncResponseClientDeleted") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Set i)) :*: S1 (MetaSel (Just "syncResponseServerAdded") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a))))) :*: ((S1 (MetaSel (Just "syncResponseServerChanged") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a))) :*: S1 (MetaSel (Just "syncResponseServerDeleted") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Set i))) :*: (S1 (MetaSel (Just "syncResponseConflicts") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a))) :*: (S1 (MetaSel (Just "syncResponseConflictsClientDeleted") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a))) :*: S1 (MetaSel (Just "syncResponseConflictsServerDeleted") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Set i)))))))

emptySyncResponse :: SyncResponse i a

newtype ServerStore i a

Constructors

ServerStore

Fields

• serverStoreItems :: Map i (Timed a)

  A map of items, named using an i, together with the ServerTime at which they were last synced.

Instances

(Eq i, Eq a) => Eq (ServerStore i a)

Defined in Data.Mergeful.Collection

Methods

(==) :: ServerStore i a -> ServerStore i a -> Bool

(/=) :: ServerStore i a -> ServerStore i a -> Bool

(Show i, Show a) => Show (ServerStore i a)

Defined in Data.Mergeful.Collection

Methods

showsPrec :: Int -> ServerStore i a -> ShowS

show :: ServerStore i a -> String

showList :: [ServerStore i a] -> ShowS

Generic (ServerStore i a)

Defined in Data.Mergeful.Collection

Associated Types

type Rep (ServerStore i a) :: Type -> Type

Methods

from :: ServerStore i a -> Rep (ServerStore i a) x

to :: Rep (ServerStore i a) x -> ServerStore i a

(ToJSON a, ToJSONKey i) => ToJSON (ServerStore i a)

Defined in Data.Mergeful.Collection

Methods

toJSON :: ServerStore i a -> Value

toEncoding :: ServerStore i a -> Encoding

toJSONList :: [ServerStore i a] -> Value

toEncodingList :: [ServerStore i a] -> Encoding

(FromJSONKey i, Ord i, FromJSON a) => FromJSON (ServerStore i a)

Defined in Data.Mergeful.Collection

Methods

parseJSON :: Value -> Parser (ServerStore i a)

parseJSONList :: Value -> Parser [ServerStore i a]

(Validity i, Show i, Ord i, Validity a) => Validity (ServerStore i a)

Defined in Data.Mergeful.Collection

Methods

validate :: ServerStore i a -> Validation

type Rep (ServerStore i a)

Defined in Data.Mergeful.Collection

type Rep (ServerStore i a) = D1 (MetaData "ServerStore" "Data.Mergeful.Collection" "mergeful-0.1.0.0-ABXYstvyIa5Kq6M8t1wQCW" True) (C1 (MetaCons "ServerStore" PrefixI True) (S1 (MetaSel (Just "serverStoreItems") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map i (Timed a)))))

newtype ClientId

A Client-side identifier for items.

These only need to be unique at the client.

Constructors

ClientId

Fields

• unClientId :: Word64

Instances

Bounded ClientId

Defined in Data.Mergeful.Collection

Methods

minBound :: ClientId

maxBound :: ClientId

Enum ClientId

Defined in Data.Mergeful.Collection

Methods

succ :: ClientId -> ClientId

pred :: ClientId -> ClientId

toEnum :: Int -> ClientId

fromEnum :: ClientId -> Int

enumFrom :: ClientId -> [ClientId]

enumFromThen :: ClientId -> ClientId -> [ClientId]

enumFromTo :: ClientId -> ClientId -> [ClientId]

enumFromThenTo :: ClientId -> ClientId -> ClientId -> [ClientId]

Eq ClientId

Defined in Data.Mergeful.Collection

Methods

(==) :: ClientId -> ClientId -> Bool

(/=) :: ClientId -> ClientId -> Bool

Ord ClientId

Defined in Data.Mergeful.Collection

Methods

compare :: ClientId -> ClientId -> Ordering

(<) :: ClientId -> ClientId -> Bool

(<=) :: ClientId -> ClientId -> Bool

(>) :: ClientId -> ClientId -> Bool

(>=) :: ClientId -> ClientId -> Bool

max :: ClientId -> ClientId -> ClientId

min :: ClientId -> ClientId -> ClientId

Show ClientId

Defined in Data.Mergeful.Collection

Methods

showsPrec :: Int -> ClientId -> ShowS

show :: ClientId -> String

showList :: [ClientId] -> ShowS

Generic ClientId

Defined in Data.Mergeful.Collection

Associated Types

type Rep ClientId :: Type -> Type

Methods

from :: ClientId -> Rep ClientId x

to :: Rep ClientId x -> ClientId

ToJSON ClientId

Defined in Data.Mergeful.Collection

Methods

toJSON :: ClientId -> Value

toEncoding :: ClientId -> Encoding

toJSONList :: [ClientId] -> Value

toEncodingList :: [ClientId] -> Encoding

ToJSONKey ClientId

Defined in Data.Mergeful.Collection

Methods

toJSONKey :: ToJSONKeyFunction ClientId

toJSONKeyList :: ToJSONKeyFunction [ClientId]

FromJSON ClientId

Defined in Data.Mergeful.Collection

Methods

parseJSON :: Value -> Parser ClientId

parseJSONList :: Value -> Parser [ClientId]

FromJSONKey ClientId

Defined in Data.Mergeful.Collection

Methods

fromJSONKey :: FromJSONKeyFunction ClientId

fromJSONKeyList :: FromJSONKeyFunction [ClientId]

Validity ClientId

Defined in Data.Mergeful.Collection

Methods

validate :: ClientId -> Validation

type Rep ClientId

Defined in Data.Mergeful.Collection

type Rep ClientId = D1 (MetaData "ClientId" "Data.Mergeful.Collection" "mergeful-0.1.0.0-ABXYstvyIa5Kq6M8t1wQCW" True) (C1 (MetaCons "ClientId" PrefixI True) (S1 (MetaSel (Just "unClientId") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Word64)))

Utility functions for implementing client-side merging

mergeAddedItems :: forall i a. Ord i => Map ClientId a -> Map ClientId (i, ServerTime) -> (Map ClientId a, Map i (Timed a))

Merge the local added items with the ones that the server has acknowledged as added.

mergeSyncedButChangedItems :: forall i a. Ord i => Map i (Timed a) -> Map i ServerTime -> (Map i (Timed a), Map i (Timed a))

Merge the local synced but changed items with the ones that the server has acknowledged as changed.

mergeDeletedItems :: Ord i => Map i b -> Set i -> Map i b

Merge the local deleted items with the ones that the server has acknowledged as deleted.

Utility functions for implementing server-side responding

addToSyncResponse :: Ord i => SyncResponse i a -> Identifier i -> ItemSyncResponse a -> SyncResponse i a

Given an incomplete SyncResponse, an id, possibly a client ID too, and an ItemSyncResponse, produce a less incomplete SyncResponse.