[darcs-users] unique features + exponential time issue

[Petr Rockai]

Hi,

Stefan Monnier <monnier at iro.umontreal.ca> writes:
> All the other systems I tried use `diff3' when merging branches and this
> doesn't make any more guesses or searches than darcs.  OTOH darcs's approach
> can sometimes better resolve apparent conflicts.  Also the fact that it
> doesn't rely on a *sequence* of patches makes it particularly good at
> cherry-picking and keeping track of merge history.

Note that the "inexact" version of 3-way is imprecise, in that it
depends on few context lines around the patch. It therefore leads to
spurious mis-merges and conflicts, where the context has nontrivially
changed (yet is still "correct"). The "exact" version of 3-way is
still susceptible to various failure modes that are avoided by darcs.

Example:

alph
beta
gamma

I independently fix the line "alph" to read "alpha", and in another
branch, i decide i want to replace "beta" with "delta". Now, when i
merge the branches, darcs correctly produces:

alpha
delta
gamma

However, when i use diff3 -m, i get:

<<<<<<< a/test
alph
delta
||||||| base/test
alph
beta
=======
alpha
beta
>>>>>>> b/test
gamma

So diff3 produces a conflict, although a clean (and correct) merge is
very much achievable.

See also http://revctrl.org/ThreeWayMerge and
http://revctrl.org/ThreeWayTextMergeImplementation on discussion of
3-way limitations.

If i understand it correctly, the "exact" 3-way version works a bit
like darcs, in that it takes diff(base,other) and commutes it with
diff(base,mine), so that it can be applied to mine (using line number
shifting, and no context lines, just like darcs does). So it can
probably avoid the above problem.

Note that the merge problem above is mostly the result of unneccessary
"guessing" on part of diff3, but i may have misunderstood you here on
what you mean with "any more guessing". Although i am fairly sure,
diff3 will happily pick wrong site for insertion, eg, when the place
is ambiguous due to context. I can try producing an example, if you
like : - ).

Maybe someone could point out a problem in my reasoning, so please set
me on the right track if you can, i may be missing some important
point here : - ).

Yours, Peter.

-- 
Peter Rockai | me()mornfall!net | prockai()redhat!com
 http://blog.mornfall.net | http://web.mornfall.net

"In My Egotistical Opinion, most people's C programs should be
 indented six feet downward and covered with dirt."
     -- Blair P. Houghton on the subject of C program indentation