search

juji-io / editscript

A library to diff and patch Clojure/ClojureScript data structures
Eclipse Public License 1.0
472 stars 23 forks source link

Three-way merging #12

Open olimsaidov opened 4 years ago

olimsaidov commented 4 years ago

I want to implement a function (diff3 a o b) where o is common ancestor of a and b. The straightforward solution is combining editscripts of two diffs: (patch o (combine (diff o a) (diff o b))). But I stuck with detecting conflicts when concurrent updates happens at same place in a and b.

Is there any known solutions or algorithms of iterating over those editscripts and finding conflicting nodes?

huahaiy commented 4 years ago

The known algorithm for three-way merge works for linear text. E.g. https://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf This may or may not be easy to adapt for tree merging. I have not investigated this in details.

Depending on what you want to do, you may not need three-way merge. For example, for synchronizing collaborative edits, Differential Synchronization should work on all kinds of data structure in principle. https://neil.fraser.name/writing/sync/