How do confluently persistent data structures handle merge conflicts?

Question

From my limited understanding fully persistent data structures allow changes to be made to previous nodes, with new nodes creating a branch rooted at the changed node, resulting in a tree of nodes and also disallowing the remerging of these branches.

       o o o
      /
o o o o o o o o o
  \
   o o o

Confluently persistent data structures on the other hand seem to allow the merging of these branches even though over time they may accumulate conflicting modifications to the contents of their given nodes.

o o o o o o o o o o o o
  \
   o o o o o x x x
      \     /
       o o o

I think I've searched the given research for an algorithm about how to potentially handle merge conflicts arising from this situation but have come up with nothing. Real world examples like git appear to punt this question to the user for manual resolution. Is this really the only option? Thanks for reading!

Answer 1

Typically, confluently persistent data structures are built so that they will never have a merge conflict. The details differ for each such data structure, but here are the broad outlines. Basically, you define a semantics for what you want to happen during a merge, then devise a data structure with those semantics. (The desired semantics depends on the kind of data stored in the data structure; there's no single answer.)

So what's a merge conflict? A merge conflict arises when your semantics for the merge throws up its hands and says "I don't know what to do". But normally, when we design confluently persistent data structures, we typically define merge semantics where that will never happen. In other words, the semantics are well-defined for all possible cases. Merge conflicts are only necessary when there are situations where the semantics aren't well-defined.

Why does git have merge conflicts? Because it is a general-purpose tool used to store arbitrary data with unknown meaning/semantics. Therefore, we can't know what the "right" semantics for merging is, in general. But confluently data structures are typically designed for a narrower, more specific purpose. Think, for instance, of a set; that has a well-defined semantics, and we can define a merge operator that fully specifies what the result of merging two sets should be for all possible cases. So, it's feasible to define merge semantics that are well-defined for all possible cases, when the data structure handles such a specific, well-defined kind of data. Git has to deal with a harder problem, where it might not be possible to define a useful, sensible merge operator that is defined for all possible cases.