30

So I've been working on a wiki type site. What I'm trying to decide on is what the best algorithm for merging an article that is simultaneously being edited by two users.

So far I'm considering using Wikipedia's method of merging the documents if two unrelated areas are edited, but throwing away the older change if two commits conflict.

My question is as follows: If I have the original article, and two changes to it, what are the best algorithms to merge them and then deal with conflicts as they arise?

3 Answers 3

36

Bill Ritcher's excellent paper "A Trustworthy 3-Way Merge" talks about some of the common gotchas with three way merging and clever solutions to them that commercial SCM packages have used.

The 3-way merge will automatically apply all the changes (which are not overlapping) from each version. The trick is to automatically handle as many almost overlapping regions as possible.

2
  • 1
    I change the URL because the one you had given is now 404. I hope it's still referring to the same article.
    – ChrisW
    Feb 7, 2010 at 17:33
  • 1
    Yup, that's it. Thanks for updating it!
    – Kyle Wiens
    Feb 8, 2010 at 2:08
12

There's a formal analysis of the diff3 algorithm, with pseudocode, in this paper: http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

It is titled "A Formal Investigation of Diff3" and written by Sanjeev Khanna, Keshav Kunal, and Benjamin C. Pierce from Yahoo.

2

Frankly, I'd rely on diff3. It's on pretty much every Unix distro, and you can always build and bundle an .EXE for Windows to ensure it is there for your purposes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.