search

automerge / autosurgeon

MIT License
269 stars 17 forks source link

Add Reconcile to Set types #40

Open XAMPPRocky opened 11 months ago

XAMPPRocky commented 11 months ago

Currently autosurgeon supports map types and list types, but there's not implmenentations for set types. It would be great if all of std::collections was represented.

alexjg commented 11 months ago

One of the reasons I haven't implemented a set type is because I'm not sure if it would be confusing. Automerge itself does not support a set, so we would have to choose what to do when we encounter duplicate elements in the document whilst hydrating or reconciling. An obvious thing to do when hydrating is to ignore the duplicates and when reconciling to remove them, but there are other choices.

Maybe instead of implementing Hydrate we should have some convenience functions for use with with, reconcile_with which do the obvious thing?

XAMPPRocky commented 11 months ago

so we would have to choose what to do when we encounter duplicate elements in the document whilst hydrating or reconciling

I mean I think it would be unexpected if you're building an application, that you'd use a set in one application, and a list in another. If you're using a set, it's sort of already handled before it reached the auto merge, having duplicate elements seem like panic situation to me, because it shouldn't happen and points to a programmer error.

alexjg commented 11 months ago

What I'm thinking of is a situation where two nodes have concurrently added the same (w.r.t Ord say, for BTreeSet, or Eq for a HashSet) element to a list in an automerge document and then the documents are merged. Because automerge doesn't have a set CRDT this would lead to duplicate elements in the underlying list even if each node was respecting the uniqueness of elements.

Now arguably automerge should have a set CRDT (although it's tough to see how more complex implementations of Ord or Hash would be supported by automerge for non primitive values). I suppose one option would be to implement a set as a map from {hash(value) -> value} and then use that as the underlying representation?

alexjg commented 11 months ago

My point is more that it seems arbitrary to force a particular representation of a Set because there might be lots of ways an application would model a set in the underlying document model of automerge. If we bless one way of modelling a set then that means anyone who doesn't want to use that representation (maybe they require interop with a JS library which does something different for example) then they'll have to write a bunch of newtypes. To me it seems nicer to have a with=... helper to handle this for everyone.

XAMPPRocky commented 11 months ago

Because automerge doesn't have a set CRDT this would lead to duplicate elements in the underlying list even if each node was respecting the uniqueness of elements.

Ah okay, in that case then yeah with makes sense.