A Formal Investigation of Diff3 (www.cis.upenn.edu)
from stsp to versioncontrol on 29 Aug 2023 18:34
https://azorius.net/g/versioncontrol/p/VyYrDSdD2XH2749LdN-A-Formal-Investigation-of-Diff3

The diff3 algorithm is widely considered the gold standard for merging
uncoordinated changes to list-structured data such as text files.
Surprisingly, its fundamental properties have never been studied in
depth. We offer a simple, abstract presentation of the diff3 algorithm
and investigate its behavior. Despite abundant anecdotal evidence that
people find diff3’s behavior intuitive and predictable in practice,
characterizing its good properties turns out to be rather delicate: a
number of seemingly natural intuitions are incorrect in general. Our
main result is a careful analysis of the intuition that edits to
“well-separated” regions of the same document are guaranteed never to
conflict.

#diff3 #mergeconflicts #merging #versioncontrol

stsp on 29 Aug 2023 18:38 next collapse

This is a classic paper I keep going back to since I first came across it many years ago.

I have not yet found a better resource which provides real insight into why merge conflicts happen and why they are represented as sections of text separated by conflict markers ever since the inception of version control tools.

tedu on 29 Aug 2023 20:03 next collapse

Btw, you can make block quotes with > .

stsp on 29 Aug 2023 20:11 next collapse

Thanks I have added them now.

It took a couple of edit attempts because it is difficult to tell apart invisible newlines from line-wrapping done by the browser text box. A preview mode before updating the live version would be nice (sorry if that already exists and I just missed it).

tedu on 29 Aug 2023 20:44 collapse

Previews are coming someday. But updates are cheap. :)

Hard line breaks in paper abstracts (and commit messages...) has always been trouble. My secret technique is to resize the edit box back and forth.

stsp on 29 Aug 2023 20:17 collapse

The line-wrapping was still looking horrible so with another edit I just redid it all in Vim and pasted that text buffer back into the browser...