Three-way merging

[olimsaidov]

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]

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/