Merge algorithms

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 9/16/2010 3:00 PM, Eli Zaretskii wrote:
> Thank you for very informative responses.
> 
> My interest in the non-default merge algorithms was triggered by the
> annoyance known as ChangeLog.  Merging one branch with another will
> almost always produce text conflicts in the ChangeLog files, if both
> branches are actively developed.

bzr-builddeb has implemented a per-file merger that handles
debian/changelog files, sorting the contents by the debian revision string.
> 
> The Right Thing for the merge in this case is very simple: put the
> lines that are new on the source branch at the beginning of the
> ChangeLog file, i.e. _before_ all the lines that are new on the target
> branch.  (The "source" branch is the one _from_ which you merge, and
> the "target" is the one _onto_ which you merge.)
> 

I suggest looking at the above code for inspiration, though I'm not sure
that your statement is 100% correct in all cases. I'm sure it *isn't* in
the case of debian => ubuntu merging, because debian may come out with a
new release that is technically older [by revnumber logic] than the
latest ubuntu version. As an example, debian may be releasing
project-1.1 while ubuntu has already upgraded to project-1.2. So debian
will add project-1.1debian2, while ubuntu has
project-1.2ubuntu3. The new debian changelog should come grouped with
the other project-1.1 entries.

> The question is, will any of the non-default merge algorithms do this
> without declaring a conflict?  If not, would it be reasonable to ask
> for a feature like that to be part of "bzr merge"?

Per-file merge hooks do what you want here. I don't think the logic is
straightforward enough in all cases that we can just have 1 "and use
this if you want it".

> 
> The alternative is currently to use "bzr extmerge" and install
> git-merge-changelog (from gnulib).  But it's a pain to build
> git-merge-changelog on Windows, and it's a nuisance to have to use a
> different command for ChangeLog files.  It would be better to have bzr
> DTRT automagically.

I don't know git-merge-changelog, but I'll note that what you really
want is some form of at least 3-way merge logic.

(and what happens if someone fixes a typo in an old changelog entry, or
remembers to credit someone, or.... You really do need to parse the
entries to know what has changed, hence a custom merge is perfectly
appropriate.)

> 
> My questions about performance was because if there is an alternative
> algorithm that can handle ChangeLog merges, I might consider making it
> the default, unless it is too slow.
> 
> Thanks.
> 

- --weave is often slower than 3-way because it evaluates more possible
texts (and searches more of the history). --lca searches the same
history, but evaluates fewer texts. --merge3 only evaluates simple texts.

Note, however, that at least --weave will detect the trivial 2-way merge
case, and just use it (IIRC). (If THIS is the latest-common-ancestor of
OTHER+THIS then just take OTHER.)

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkySeg0ACgkQJdeBCYSNAAOsbgCfV5pGYdGMfeEeBpgq007jUO5/
AM8AoLCwSqJamvn79f2tzjcuH4XxJlb0
=VwZL
-----END PGP SIGNATURE-----