merge lies about lacking common ancestors when it has multiple choices

[Matthew Fuller]

When two branches have multiple common ancestors, merge lies through its teeth and says there are none:

bzr: ERROR: Branches have no common ancestor, and no merge base revision was specified.

#!/bin/sh -ex
bzr="/usr/local/bin/bzr --no-plugins --no-aliases"

if [ -d base1 -o -d base2 -o -d p1 -o -d p2 ]; then
 echo "Cleanup plz"
 exit
fi

# Make 2 base branches
for i in 1 2; do
 ${bzr} init base${i}
 (
  cd base${i} ;

  touch b${i}_x ;
  ${bzr} add b${i}_x ;
  ${bzr} ci -m "b${i}_x" ;
 )
done

# Make two work branches, both based on both bases, each with their own work
for i in 1 2; do
 ${bzr} branch base1 p${i}
 (
  cd p${i} ;

  ${bzr} merge -r0..-1 ../base2 ;
  ${bzr} ci -m 'merge base2' ;

  touch p${i}_x ;
  ${bzr} add p${i}_x ;
  ${bzr} ci -m "p${i}_x"
 )
done

# Now try and merge them together
(
 cd p1 ;
 ${bzr} merge ../p2
 # There wasn't supposed to be an earth-shattering KA-BOOM!
)

[Andrew Bennetts (spiv)]

Thanks for the script, I can reproduce this.

This appears to be a criss-cross, but of two revisions that have no parents (other than null:). So in a sense the LCA is null:, which the logic then interprets as no LCA.

Bad ascii art:

 P1 P2
 | |
 M1 M2
 | \ /|
 | x |
 | / \|
 B1 B2

(or just run "bzr qlog p1 p2" after running fullermd's shell script)

[Matthew Fuller (fullermd)]

> This appears to be a criss-cross, but of two revisions that have no
> parents (other than null:).

In this repro script, the two branches share 2 common initial
revisions. In the actual case I ran into it, the branches had 2 and 3
(respectively) initial revs, with 2 of them being common, and for the
branch with 3 initials, the leftmost initial rev was the uncommon one.
But I don't believe either the extra uncommon path or the chirality
matters.

[John A Meinel (jameinel)]

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

fullermd wrote:
>> This appears to be a criss-cross, but of two revisions that have no
>> parents (other than null:).
>
> In this repro script, the two branches share 2 common initial
> revisions. In the actual case I ran into it, the branches had 2 and 3
> (respectively) initial revs, with 2 of them being common, and for the
> branch with 3 initials, the leftmost initial rev was the uncommon one.
> But I don't believe either the extra uncommon path or the chirality
> matters.
>

Both branches do end up containing the initial (unrelated) commits.
Andrew is pointing out that the criss-cross means that neither of them
is a valid base to be used for merging, which means that we have to go
back further, and there *isn't* a single base that would work (aside
from NULL).

I'm curious what you would get w/ "bzr merge --weave" though my guess is
that the initial (find *some* common base) will still error out and not
let you continue without an explicit base selection.

John
=:->

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

iEYEARECAAYFAksBh7sACgkQJdeBCYSNAANZCgCeKrpporvECo88N7dHtQoctTQF
r80An3A9+shVjwwqswnnDRiWwHfae79L
=QsOD
-----END PGP SIGNATURE-----

[Matthew Fuller (fullermd)]

> Andrew is pointing out [...]

Oh, I understood. Was just adding background in case it mattered.

> I'm curious what you would get w/ "bzr merge --weave" though my
> guess is that the initial (find *some* common base) will still error
> out and not let you continue without an explicit base selection.

You guess correctly.

[Alexander Belchenko (bialix)]

This bug affects one of the component of our project. We have no criss cross merge there though. I can provide these 2 branches for analysis. They have not very big history.

[John A Meinel (jameinel)]

Alexander, I would be interested to see the ancestry (even privately). Are you sure there isn't a criss-cross? It can happen in unexpected ways. (Landing >1 feature branch into 2 integration branches can do so, though the art is a bit hard to draw.)

[Alexander Belchenko (bialix)]

John, sorry, it seems I've missed your mail in the March, and now I can't recall where my problematic branch is (we have many components with many branches :-/)

[David Strauss (davidstrauss)]

I'm now seeing this issue on a Drupal.org branch. I can give access to individuals, but I cannot make the actual branches public.

[David Strauss (davidstrauss)]

There is a workaround to this:

(1) Cherry pick and copy files as necessary to get the "merge" in order.
(2) Edit merge.py to force it to pick a specific LCA.
(3) Perform the merge, revert any changes (in the merge-protecting way), and commit.

Step two is possible by adding a line to merge.py:
             lcas = self.revision_graph.find_lca(revisions[0], revisions[1])
+ lcas = set([list(lcas)[0]])
             self._is_criss_cross = False

You may need to force a different revision (other than the one in index zero) depending on the merge topology.