[Gnu-arch-users] Star-merge Fatally Wounded

[David Allouche]

Star-merge was not up to the job we assigned to it. It was fatally
wounded in a merging riot at Canonical. Peacekeeping forces were only
able to rescue the merge operator after he received injuries to several
vital organs. The forensics have uncovered astonishing evidence.

FLASH: we have just been informed that the citizen Aaron Bentley has
been aware of the the problem for weeks. He is currently under arrest
pending his trial on charges of complicity of spurious merge conflict
and dissimulation of design problem. ;-)

For the impatient, the curious and the skeptical, a test case is
attached, which demonstrates how a racy merge scenario can make star-
merge cause spurious conflicts even though the star-topology was not
broken.

        Merge scenario
        
        A-0 =====> B-0 
         |          |
         |          |
        A-1 --  -- B-1  
         |    \/    |
         |    /\    |
        A-2 <-  -> B-2

If you think that is an excessively hairy scenario, we have practical
experience that this situation can happen very easily with pqm.

When trying to merge B into A we get:
* star-merge by delta(A-1, B-2)[TA]j
which applies B-0 and B-1 even though they are already present.

When trying to merge A into B we get:
* star-merge by delta(B-1,A-2)[TB]
which applies A-1 even though it is already present.

TA and TB denote working trees based respectively on A-2 and B-2.

Actually, this merge problem cannot be solved by apply-delta. Yes, that
is an instance of the idempotent merge problem, but that is true of
every known merge scenario. Let us see if there is not simple way to
solve this problem.

Let us consider merging B into A. The goal of the merge is to apply B-2
without re-applying A-0, A-1, A-2, B-0, or B-1.

We want to add the patchlog for B-2, therefore
      * dest = B-2
      * orig != B-2
We do not want to discard local changes,
      * orig != TA
We do not want to to apply A-1, and B-2 contains A-1,
      * orig contains A-1
Similarly, we do not want to apply B-1, and B-2 contains B-1,
      * orig contains B-1
The only orig which meets those conditions is A-2, however B-2 does not
contain A-2, so delta(A-2, B-2) removes the  additional changes in A-2.

So, we cannot merge B into A by apply-delta.

By symmetry between A and B, we cannot merge A into B by apply-delta.

There are solutions to this problem if we can assume that one of the
branches does only pure, conflictless merges. That's lucky for us
because that is a property of branches managed by PQM so we can solve
our problem.

Can anybody find a general solution to the problem of merging between
two branches without assuming pure merges, and without resorting to
full-blown idempotent merge?

-- 
                                                            -- ddaa

cross-merge-case.sh
Description: application/shellscript