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

[Tom Lord]

    > From: David Allouche <address@hidden>

    >         Merge scenario

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


[Nicely lucid message and elegant proof, by the way.  Thanks for
 taking the time.]

Abentley's short answer sums it up nicely:

  To put it another way, star-merge works when one revision from
  REFERENCE or OTHER is the most recent merge.  When merges happen in
  parallel, there is no most recent merge, and the algorithm breaks.

Although I disagree with some of the rest (see below).

This reply is a bit long.   You touched on an interesting topic.

I believe that what you have in that scenario (since you are planning
on using star-merge and maintaining a star topology) is, alas, a user
error.  But let me explan and qualify that and ack that you do have a
real technical problem that needs attention and make a few suggestions
about how to solve it.

Here's the user error:  Which existed first?  A-2 or B-2?   

Without loss of generality, let's assume that A-2 existed first.

Then B-2 was created, *in effect*, by:

        % tla get B-1 
        % cd B-1
        % tla star-merge A-1            [***]
        % tla commit

The [***] step is the "user error" because, at that time, A-1 is not
the latest revision.  A-2 was the latest revision (in the absolute
scheme of things) when that merge was done.

A truly star-topology merge management policy would have required 
this instead:

        % tla get B-1 
        % cd B-1
        % tla star-merge A-2            [***]
        % tla commit

and your merge diagram would look like this:

    > From: David Allouche <address@hidden>

    >         Merge scenario

    >         A-0 =====> B-0 
    >          |          |
    >          |          |
    >         A-1     -- B-1  
    >          |     /    |
    >          |    /     |
    >         A-2 <-      |
    >             `----> B-2

The criticial difference, visually, is that in the second diagram, the
merge lines do not cross.   Possibly/probably someone can construct an
elegant graph-theory model of when star-merge applies (hence the
rather grandiose name :-).

To quote the tutorial in the chapter about star-merge:

  Whenever we have a such a diagram in which none of the merge lines
  cross, that is a "simple development branch".

In that second scenario, star merging B into A would be:

   delta(A-2, B-2)[TA]                  (e.g., get local changes from B-2)

and merging A into B would be:

   delta(A-2, A-2)[TB]                  (e.g., a noop)

both of which are copacetic, right?

I infer from this and general knowledge of what you're working on that
you probably wound up with this diagram:

    >         Merge scenario

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

by merging against out of sync mirrors or by doing roughly concurrent
merges to both A and B.

You do, indeed, give a lovely proof (quoted below) that star-merge
can't handle that diagram.   We already knew that, in some sense.
It's nice to see it spelled out cleanly.

You ask: 

    > 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?

A proof that nobody can find a general solution is not much harder
than the proof you have given for why star-merge isn't a general
solution.  I don't have time ( :-) right now to write (again) such a
proof myself but here's a hint: in addition to drawing merge diagrams,
you might try adding some sample file contents.  It isn't that hard to
construct examples of file contents for which automated merging in
scenarios like this one is impossible unless the merge tool is an AI
program that understands what the programmers are trying to do.

Short answer, for your immediate needs: if I were you, I'd first try
to eliminate the race conditions in your merges.  Either your
infrastructure should never attempt a "[***]" merge (described above)
or else your infrastructure should have an exception handler to
recover from this case.

I'm a *tiny* bit concerned about the scenario because it is something
that can easily happen quite by accident.   For example, it could
happen between my and jblack's tla branches if the timing of our
mutual merges and mirror pushes worked out that way.    I'm only a
tiny bit concerned because that doesn't seem to be that likely;  the
mildly attententive programmer will notice it if it does;  and it
doesn't seem that hard to recover from by-hand.   Still.... it is at
least a very interesting note to keep in mind for process design.

Abentley proposes:

  The star-merge command should be updated to detect this situation
  and error-out when it occurs.  This can be done by determining
  LAST_MERGE_INTO_REFERENCE, comparing it with MAYBE_ANCESTOR_2, and
  determining ANCESTOR'.  If ANCESTOR' is not ANCESTOR, then there is
  no valid ANCESTOR.

I don't believe that, what with mirrors and all, the star-merge
command can reliably detect this situation.   star-merge is operating
under a condition of "imperfect information", no matter what.

Consequently, what you (Abentley) propose is to take the very regular
behavior of a command, add an arbitrary exception, and that exception
doesn't really solve the problem.  I'd rather have the regular command
without the hairy yet imperfect exceptions.  That's easier and simpler
and: hey -- programming tools are intrinsicly dangerous in the first
place: you're not going to solve *that* no matter how many little
quirks you add to them.

Who knows?  Maybe the edge cases where star-merge does something
deterministic but not currently recognizable as useful may, one day,
prove to be useful for something unanticipated (actually, I think this
is *very* *very* probable --- it's useful when using arch as a general
purpose db).  In the meanwhile, saws cut, hammers pound, and
star-merge does what it does.  The trick for users is to avoid sawing
nails, hammering boards, or star-merging when star-merge doesn't
apply.

Relevent quotes: 
  "If you can't stand the heat...." 
  and
  "Doctor, it hurts when I do *this*....."
Relevent visual:
  the graphics animation at the top of http://jwz.livejournal.com/
-t




    > 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
    > 
    > 
    > --=-f6Q+sYW0MlhBsRQEsxMi
    > Content-Description: 
    > Content-Type: application/x-shellscript
    > Content-Disposition: attachment; filename=cross-merge-case.sh
    > Content-Transfer-Encoding: base64
    > 
    > 
IyEvYmluL2Jhc2gKCnNldCAtZQpob21lPS90bXAvdGxhLWJ1Z3MtYGlkIC11bmAKYXJjaD1qZG9l
    > 
QGV4YW1wbGUubmV0CnZzbkE9JGFyY2gvZm9vLS1BLS0wCnZzbkI9JGFyY2gvZm9vLS1CLS0wCnRy
    > 
ZWVBPSRob21lL3RyZWVBCnRyZWVCPSRob21lL3RyZWVCCmZpbGVBPSR0cmVlQS9maWxlLUEKZmls
    > 
ZUI9JHRyZWVCL2ZpbGUtQgoKIyBTZXQgdXAgc2FuZGJveApybSAtcmYgJGhvbWUKbWtkaXIgJGhv
    > 
bWUKSE9NRT0iJGhvbWUiCmNkICRob21lCgojIFNldCB1cCB0bGEKdGxhIG15LWlkICdKb2huIERv
    > 
ZSA8amRvZUBleGFtcGxlLm5ldD4nCnRsYSBtYWtlLWFyY2hpdmUgJGFyY2ggJGhvbWUvJGFyY2gK
    > 
bWtkaXIgJHRyZWVBCnRsYSBpbml0LXRyZWUgLS1kaXIgJHRyZWVBICR2c25BCnRsYSBpZC10YWdn
    > 
aW5nLW1ldGhvZCAtLWRpciAkdHJlZUEgbmFtZXMgIyBqdXN0IHRvIGJlIGxhenkKZWNobyAnYmFz
    > 
ZS0wJyA+ICRmaWxlQQplY2hvID4gJHRyZWVBL2ZpbGUtQiAjIG9yIG5vIGNvbmZsaWN0IGhhcHBl
    > 
bnMhCnRsYSBpbXBvcnQgLS1kaXIgJHRyZWVBIC1TCnRsYSB0YWcgLVMgJHZzbkEgJHZzbkIKdGxh
    > 
IGdldCAkdnNuQiAkdHJlZUIKCiMgTWVyZ2Ugc2NlbmFyaW8KIwojIEEtMCA9PT09PT4gQi0wCiMg
    > 
IHwgICAgICAgICAgfAojICB8ICAgICAgICAgIHwKIyBBLTEgLS0gIC0tIEItMQojICB8ICAgIFwv
    > 
ICAgIHwKIyAgfCAgICAvXCAgICB8CiMgQS0yIDwtICAtPiBCLTIKCmVjaG8gJ3BhdGNoLTEnID4g
    > 
JGZpbGVBCnRsYSBjb21taXQgLS1kaXIgJHRyZWVBIC1zICdwYXRjaCcKZWNobyAncGF0Y2gtMSc+
    > 
ICRmaWxlQgp0bGEgY29tbWl0IC0tZGlyICR0cmVlQiAtcyAncGF0Y2gnCnRsYSBzdGFyLW1lcmdl
    > 
IC0tZGlyICR0cmVlQSAkdnNuQgplY2hvICdwYXRjaC0yJz4gJGZpbGVBCnRsYSBzdGFyLW1lcmdl
    > 
IC0tZGlyICR0cmVlQiAkdnNuQQplY2hvICdwYXRjaC0yJz4gJGZpbGVCCnRsYSBjb21taXQgLS1k
    > 
aXIgJHRyZWVBIC1zICdtZXJnZScKdGxhIGNvbW1pdCAtLWRpciAkdHJlZUIgLXMgJ21lcmdlJwoK
    > 
c3RhdHVzPTAKaWYgISB0bGEgc3Rhci1tZXJnZSAtLWRpciAkdHJlZUEgJHZzbkIgOyB0aGVuCiAg
    > 
ICAjIEJsb3dzLCAkdnNuQi0tcGF0Y2gtMSBpcyBhcHBsaWVkIGFnYWluIQogICAgc3RhdHVzPTEK
    > 
ICAgIGVjaG8gJyoqKioqKiBzdGFyLW1lcmdlIEIgaW50byBBIGZhaWxzICoqKioqKicKZmkKCmlm
    > 
ICEgdGxhIHN0YXItbWVyZ2UgLS1kaXIgJHRyZWVCICR2c25BIDsgdGhlbgogICAgIyBCbG93cywg
    > 
JHZzbkEtLXBhdGNoLTEgaXMgYXBwbGllZCBhZ2FpbiEKICAgIHN0YXR1cz0xCiAgICBlY2hvICcq
    > 
KioqKiogc3Rhci1tZXJnZSBBIGludG8gQiBmYWlscyAqKioqKionCmZpCgpleGl0ICRzdGF0dXMK
    > 
    > 
    > 
    > --=-f6Q+sYW0MlhBsRQEsxMi
    > Content-Type: text/plain; charset="us-ascii"
    > MIME-Version: 1.0
    > Content-Transfer-Encoding: 7bit
    > Content-Disposition: inline
    > 
    > _______________________________________________
    > Gnu-arch-users mailing list
    > address@hidden
    > http://lists.gnu.org/mailman/listinfo/gnu-arch-users
    > 
    > GNU arch home page:
    > http://savannah.gnu.org/projects/gnu-arch/
    > --=-f6Q+sYW0MlhBsRQEsxMi--
    > 
    > 
    > 
    >