Re: n-heads and patch dependency chains

[Catalin Marinas <catalin.marinas@arm.com>]

Sam Vilain <sam@vilain.net> wrote:
> "Patch dependency chains", the best plain-English term we could find for
> the scary sounding darcs term "patch calculus", are said by some to be a
> very good reason to use a system like darcs, even to some its
> fundamental advantage over systems such as git.

As Linus pointed out, while darcs theory is interesting, it doesn't
work properly in practice. Dependency tracking can create problems
with merging. Darcs' patch commuting theory has (a big, IMHO) problem
since every time you pull a patch (or more) it needs to commute all
the patches back to the common ancestor. Over time, the merging
becomes slower and slower (i.e. even much slower than what darcs shows
in simple tests with the Linux kernel).

Inexact patch commuting can be achieved using diff3 (or merge) with 3
snapshots of the tree (the bottom of the patch, the top of the patch
and the current head on top of which the patch is being applied) which
GIT handles very well and fast since there is no need to commute
thousands of patches back to the common ancestor. The slight
disadvantage is that diff3 merging is not as exact as Darcs' patch
commuting but OK for 99% of the real cases.

StGIT is based on this inexact patch commuting "theory" and, with the
addition of upstream merging detection (based on reverse-applying), it
is seems to behave properly in almost all the cases (though you can
deliberately create some patches to break the algorithm).

I've been thinking about adding patch dependency tracking to StGIT but
only as a recommendation and not enforcement. The algorithm would be
similar to the upstream merging detection.

-- 
Catalin