Re: Comments in read-tree about #nALT

From: Junio C Hamano <junkio@cox.net>
Date: Aug 27, 2005, 08:59 UTC
Message-ID: <7vy86nvjpe.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <7vwtm726xq.fsf@assigned-by-dhcp.cox.net>

Junio C Hamano <junkio@cox.net> writes:

Show 17 quoted lines

> Daniel Barkalow <barkalow@iabervon.org> writes:
>
>> Part of threeway_merge, however, wants to search the rest of the cache for
>> interfering entries in some cases, which would have to happen differently,
>> because I won't have the cache completely filled out beforehand. I'm
>> trying to figure out what the comments are talking about, and they seem to
>> refer to a list of the possible cases. Is that list somewhere convenient?
>
> Please look for END_OF_CASE_TABLE in t/t1000-read-tree-m-3way.sh;
> the table talks about some of the (ALT) not implemented, but
> some of them are ("git whatchanged t/t1000-read-tree-m-3way"
> would tell you which).
>
> Two way cases are described in Documentation/git-read-tree.txt,
> if you care.  If you were not touching the three-way case right
> now, I'd move/copy the three way cases there as well, but that
> can wait until after your changes.

The comments like /* 4 and 5 */ in twoway_merge refer to the case table number in the Documentation/git-read-tree.txt

Just in case you are wondering what all this index constraints are about. It used to be that the order of stages given to "read-tree -m O A B" did not have any inherent meaning, but it is not anymore, especially after the "-u" flag was introduced and the "new world order" was introduced to the merge operation. Before that, we tried to do everything in the index file, and even merge-one-file-script tried not to touch the files in the working tree at all while it worked. But that has changed, and these days I believe the code assumes that A corresponds to the commit the current working tree is based upon, and tries to make sure that the index file does not have a local modification that would be lost by the result of "read-tree -m -u O A B" (that is, roughly speaking, read-tree chose B and the working tree was modified since A).

If you need more information, probably the first thing to do would be to run "git whatchanged" on read-tree, its tests and documentations to find the rough timescale of those "new world order" changes, and check the list archives.

As a software archaeologist, I've done some of that for you and for myself. I hope these would help you.

Gee, up until now I thought my only significant contribution was around diff, but going through 5000+ messages made me realize I was all over the place ;-).

------------------------------------------------

This message talked about Linus' desire not to touch working tree at all.

    Date:	Sun, 1 May 2005 13:29:59 -0700 (PDT)
    From:	Linus Torvalds <torvalds@osdl.org>
    Subject: Re: [PATCH] Really fix git-merge-one-file-script this time.
    Message-ID: <Pine.LNX.4.58.0505011312080.2296@ppc970.osdl.org>

This was a question to Linus after the "new merge world order" happened.

    Message-ID: <7v64wrvpt4.fsf@assigned-by-dhcp.cox.net>
    From: Junio C Hamano <junkio@cox.net>
    Subject: new read-tree questions.
    Date: Mon, 06 Jun 2005 01:43:03 -0700

And these three discusses the issues. The first two are the must-read responses from Linus.

    Message-ID: <Pine.LNX.4.58.0506060748390.1876@ppc970.osdl.org>
    From: Linus Torvalds <torvalds@osdl.org>
    Subject: Re: new read-tree questions.
    Date: Mon, 6 Jun 2005 08:04:22 -0700 (PDT)

    Message-ID: <Pine.LNX.4.58.0506060738170.1876@ppc970.osdl.org>
    From: Linus Torvalds <torvalds@osdl.org>
    Subject: Re: Last mile for 1.0
    Date: Mon, 6 Jun 2005 07:47:52 -0700 (PDT)

    Message-ID: <7voeajp875.fsf@assigned-by-dhcp.cox.net>
    From: Junio C Hamano <junkio@cox.net>
    Subject: Re: clarifying two tree merge semantics
    Date: Mon, 06 Jun 2005 12:59:58 -0700

The thread starting at this message is about emu23, which may not affect directly what you are doing, but if you are interesting the issues there are interesting.

    Message-ID: <Pine.LNX.4.58.0506081336080.2286@ppc970.osdl.org>
    From: Linus Torvalds <torvalds@osdl.org>
    Subject: Handling merge conflicts a bit more gracefully..
    Date: Wed, 8 Jun 2005 13:55:23 -0700 (PDT)

I've reproduced the whole message for this one, which is what your question was about.

    Message-ID: <7voeagrp11.fsf_-_@assigned-by-dhcp.cox.net>
    From: Junio C Hamano <junkio@cox.net>
    Subject: [PATCH 0/3] Handling merge conflicts a bit more gracefully
    Date: Thu, 09 Jun 2005 00:02:34 -0700

This series consists of three patches.

  [PATCH 1/3] read-tree.c: rename local variables used in 3-way merge code.
  [PATCH 2/3] read-tree -m 3-way: loosen index requirements that is too strict.
  [PATCH 3/3] read-tree -m 3-way: handle more trivial merges internally

You may have noticed that I already described some "alternative semantics" in the 3-way merge test script t1000. This set of patches implements some of them, namely the following 5 cases:

     O       A       B         result      index requirements
-------------------------------------------------------------------
  5  missing exists  A==B      take A      must match A, if exists.
 ------------------------------------------------------------------
  6  exists  missing missing   remove      must not exist.
 ------------------------------------------------------------------
  8  exists  missing O==B      remove      must not exist.
 ------------------------------------------------------------------
 10  exists  O==A    missing   remove      must match A and be
                                           up-to-date, if exists.
 ------------------------------------------------------------------
 14  exists  O==A    O!=B      take B      if exists, must either (1)
                                           match A and be up-to-date,
                                           or (2) match B.
-------------------------------------------------------------------

The first patch is to match the local variable names used in the functions involved to the names used in the case matrix.

Case #14 is resolved identically as the old code does, but the index requirement old code placed on this case was stricter than necessary. In this case, satisfying the usual rule of "match A and be up-to-date if exists" is certainly OK, but additionally, if the original index matches the tree being merged (without even being up-to-date) is also permissible, because there would be no information loss or work-tree clobbering if we allowed it. The second patch in the series corrects this.

Case #5, #6, #8, and #10 were traditionally kept unmerged in the index file when read-tree is done, and resolving them was left to the script. By resolving these internally, we can loosen the index requirements without compromising correctness for case #5. Other three cases could still be left for the "script policy" because this change does not affect the index requirements for these cases, but it was simple enough to implement them and this would not be too controversial a change. The third patch in the series implements these changes.