Comments in read-tree about #nALT

Comments in read-tree about #nALT

[Daniel Barkalow]

I've gotten to the point of having all of the entries for a given path
ready to put into the cache at the same, and now I want to convert the
merge functions to take their data directly, rather than in the cache, so
that they can take extra entries for extra ancestors.

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?

	-Daniel
*This .sig left intentionally blank*

Re: Comments in read-tree about #nALT

[Junio C Hamano]

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.

Re: Comments in read-tree about #nALT

[Junio C Hamano]

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

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

Re: Comments in read-tree about #nALT

[Daniel Barkalow]

On Sat, 27 Aug 2005, Junio C Hamano wrote:

> 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).

It looks like all of them are implemented:

#2ALT, #3ALT, #5ALT, and #14ALT, according to the commit comments, and the
others seem from the email you quote to have been done in the process of
getting #5ALT.

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

I'd actually like to introduce Documentation/technical/trivial-merge for
this stuff; I think it would be good to have documentation for people who
need to know how the stuff works, rather than just how to use it, so we
get a balance between reams of information that users don't want to wade
through and being too vague for future developers.

Okay, so it looks to me like the only cases that care about the contents
of the index, other than in stage 0 (which is effectively another tree,
but already in index-form rather than tree-form), are 2 and 3, and these
only care because read-tree modifies the stage of entries, rather
than removing them and adding a stage-0 replacement entry; if it went
through the add logic without SKIP_DFCHECK, that would reject the same
things that causes_df_conflict rejects (at the point where whichever is
second is done).

So if I do the merge on tree entries (plus a stage-0 ce for the input from
the index), and then add the result(s) to the cache, I can skip
causes_df_conflict() in favor of just not using SKIP_DFCHECK. Is this
right?

Also, there doesn't actually seem to be a DF test in t1000; I think the
t1005 DF test covers these cases (by the emu23 path into this code). Is
this right?

	-Daniel
*This .sig left intentionally blank*

Re: Comments in read-tree about #nALT

[Daniel Barkalow]

On Sat, 27 Aug 2005, Daniel Barkalow wrote:

> Okay, so it looks to me like the only cases that care about the contents
> of the index, other than in stage 0 (which is effectively another tree,
> but already in index-form rather than tree-form), are 2 and 3, and these
> only care because read-tree modifies the stage of entries, rather
> than removing them and adding a stage-0 replacement entry; if it went
> through the add logic without SKIP_DFCHECK, that would reject the same
> things that causes_df_conflict rejects (at the point where whichever is
> second is done).
>
> So if I do the merge on tree entries (plus a stage-0 ce for the input from
> the index), and then add the result(s) to the cache, I can skip
> causes_df_conflict() in favor of just not using SKIP_DFCHECK. Is this
> right?

What I missed was that the effect of causes_df_conflict is to give "no
merge" for the entry, rather than giving an error overall. So I do need an
equivalent.

> Also, there doesn't actually seem to be a DF test in t1000; I think the
> t1005 DF test covers these cases (by the emu23 path into this code). Is
> this right?

Looks like stuff all over the place fails if causes_df_conflict is messed
up, so I should be covered.

	-Daniel
*This .sig left intentionally blank*

Re: Comments in read-tree about #nALT

[Linus Torvalds]

On Sat, 27 Aug 2005, Daniel Barkalow wrote:
> 
> What I missed was that the effect of causes_df_conflict is to give "no
> merge" for the entry, rather than giving an error overall. So I do need an
> equivalent.

Daniel, 
 I'm not 100% sure what you're trying to do, but one thing that might work 
out is to just having multiple "stage 3" entries with the same pathname.

We current use 4 stages:
 - stage 0 is "resolved"
 - stage 1 is "original"
 - stage 2 is "one branch"
 - stage 3 is "another branch"

But if we allowed duplicate entries per stage, I think we could easily 
just fold stage 2/3 into one stage, and just have <n> entries in stage 2. 
That would immediately mean that a three-way merge could be <n> way.

The only rule would be that when you add a entry to stage 2, you must 
always add it after any previous entry that is already in stage 2. That 
should be easy.

In fact, this extension might even allow us to solve the "multiple merge
base" problem: we could allow multiple entries in "stage 1" too, ie one
entry per merge base (and just collapse identical entries - there's no 
ordering involved in stage 1 entries).

So you could merge "n" trees with "m" bases, and all without really 
changing the current logic much at all.

Maybe I'm missing something (like what you're trying to do in the first 
place), but this _seems_ doable.

Of course, "git-merge-one-file" gets more interesting as a result.

			Linus

Re: Comments in read-tree about #nALT

[Daniel Barkalow]

On Sat, 27 Aug 2005, Linus Torvalds wrote:

> On Sat, 27 Aug 2005, Daniel Barkalow wrote:
> >
> > What I missed was that the effect of causes_df_conflict is to give "no
> > merge" for the entry, rather than giving an error overall. So I do need an
> > equivalent.
>
> Daniel,
>  I'm not 100% sure what you're trying to do, but one thing that might work
> out is to just having multiple "stage 3" entries with the same pathname.
>
> We current use 4 stages:
>  - stage 0 is "resolved"
>  - stage 1 is "original"
>  - stage 2 is "one branch"
>  - stage 3 is "another branch"
>
> But if we allowed duplicate entries per stage, I think we could easily
> just fold stage 2/3 into one stage, and just have <n> entries in stage 2.
> That would immediately mean that a three-way merge could be <n> way.
>
> The only rule would be that when you add a entry to stage 2, you must
> always add it after any previous entry that is already in stage 2. That
> should be easy.

It looks like stage 2 is currently special as the stage that's similar to
the index/HEAD/working tree. However, I don't see any problem with <n>
entries in stage 3, except that, if you have a non-maximal number of them
for some reason, it'll be impossible to determine which came from which
tree.

> In fact, this extension might even allow us to solve the "multiple merge
> base" problem: we could allow multiple entries in "stage 1" too, ie one
> entry per merge base (and just collapse identical entries - there's no
> ordering involved in stage 1 entries).

That's actually the problem I was working on.

> So you could merge "n" trees with "m" bases, and all without really
> changing the current logic much at all.
>
> Maybe I'm missing something (like what you're trying to do in the first
> place), but this _seems_ doable.

I'd be afraid of confusing everything by removing the uniqueness
invariant, although I guess not too much does anything with entries in
stages other than 0. I probably just don't find the index as intuitive as
you do and as the struct tree representation.

I'm working on arranging the code to look at each path in sequence, with
the input trees as the inner loop, rather than with the loops in the other
order; using parse_tree to parse the objects instead of read_tree; and
doing trivial merges before putting things in the cache, rather than
after. I'd been thinking that this would avoid a limit on the number of
stages, since I hadn't considered whether multiple entries for the same
path and stage could be allowed.

I still think that my order is likely to be easier to understand and
involve read-tree relying less on tricky properties of the data
structures, but I'll have to get it done before I can say that for sure.

	-Daniel
*This .sig left intentionally blank*

Re: Comments in read-tree about #nALT

[Linus Torvalds]

On Sat, 27 Aug 2005, Daniel Barkalow wrote:
> 
> It looks like stage 2 is currently special as the stage that's similar to
> the index/HEAD/working tree.

Ahh, yes. We do actually want that. So yes, we should make only stage 3 
have the multiple entries.

> I'd be afraid of confusing everything by removing the uniqueness
> invariant, although I guess not too much does anything with entries in
> stages other than 0. I probably just don't find the index as intuitive as
> you do and as the struct tree representation.

Yes, I find the index to be very nice to work with - it basically allows
you to work with multiple trees in one go, instead of working one file at
a time. You just slurp in any number of trees (with some trivial rules
about which stage they go in), and then you can just walk through each
filename and efficiently handle one file at a time without re-doing the
tree thing. Very nice.

			Linus

Re: Comments in read-tree about #nALT

[Junio C Hamano]

Daniel Barkalow <barkalow@iabervon.org> writes:

> What I missed was that the effect of causes_df_conflict is to give "no
> merge" for the entry, rather than giving an error overall. So I do need an
> equivalent.

Correct.

Re: Comments in read-tree about #nALT

[Junio C Hamano]

Daniel Barkalow <barkalow@iabervon.org> writes:

> I'd actually like to introduce Documentation/technical/trivial-merge for
> this stuff; I think it would be good to have documentation for people who
> need to know how the stuff works, rather than just how to use it, so we
> get a balance between reams of information that users don't want to wade
> through and being too vague for future developers.

I think that is an excellent idea to have user manual vs
internals manual.

Re: Comments in read-tree about #nALT

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Daniel, 
> I'm not 100% sure what you're trying to do, but one thing that might work 
> out is to just having multiple "stage 3" entries with the same pathname.

My understanding is that he is enhancing the current three-way
merge 'read-tree -m O A B' "we are at A and have come from O; we
would like to apply changes made by somebody who went from O to
A" to 'read-tree -m O1,O2,O3,... A B' to mean "any of the O_n
are merge-base candidates".  I think having multiple "stage 1"
is useful for what Daniel is doing.

> But if we allowed duplicate entries per stage, I think we could easily 
> just fold stage 2/3 into one stage, and just have <n> entries in stage 2. 
> That would immediately mean that a three-way merge could be <n> way.

I suspect you are solving a different problem here --- an
Octopus.

But I agree that the current way of doing things in stage 2 and
stage 3 is special casing two head merges from an Octopus, and
there might not be a fundamental reason for doing so.  Folding
the current stage 2 and 3 into a single "merge target stage",
treating current stage 1 as "merge base stage", and allowing
duplicate entries in both stages might turn out to make more
sense.  I suspect this would break a lot of tools initially, but
that is part of the process of making progress.

> The only rule would be that when you add a entry to stage 2, you must 
> always add it after any previous entry that is already in stage 2. That 
> should be easy.

The same rule should apply to multiple stage 1 entries to
represent multiple candidate merge bases.

Re: Comments in read-tree about #nALT

[Linus Torvalds]

On Mon, 29 Aug 2005, Junio C Hamano wrote:
> 
> > But if we allowed duplicate entries per stage, I think we could easily 
> > just fold stage 2/3 into one stage, and just have <n> entries in stage 2. 
> > That would immediately mean that a three-way merge could be <n> way.
> 
> I suspect you are solving a different problem here --- an
> Octopus.

Well, that too, but I did mention doing the same thing for stage 1, which 
is the "multiple merge bases" case. 

It all boils down to the same thing: we want to read in multiple trees, 
and then do merges one file at a time based on the result (and the fact 
that we can have multiple entries for files in the different stages 
essentially just complicates "git-merge-one-file").

> But I agree that the current way of doing things in stage 2 and
> stage 3 is special casing two head merges from an Octopus, and
> there might not be a fundamental reason for doing so.  Folding
> the current stage 2 and 3 into a single "merge target stage",

Daniel pointed out that there is a real reason for stage 2 - it's used as 
a special case for "matches current index". Apart from that, it's the same 
as stage 3.

Stage 3 is the one we can duplicate freely. There's can be only one branch
that is special in that it matches the current index, so expanding stage 3 
from one to many is clearly something where all the different trees are on 
equal footing.

Same goes for stage 1 - all merge bases are conceptually equally valid, 
and thus there is no reason to consider any "ordering" between them, and 
you can merge any number of trees into stage 1.

So stage 0 and stage 2 are special in that they inherently have "one
special tree" that they correspond to.

		Linus