Moved files and merges

Moved files and merges

[H. Peter Anvin]

I currently have two klibc trees,

rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc.git

and

rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc-kbuild.git


One of the differences between the trees is that a bunch of files have 
been rearranged.  Unfortunately, it seems that whenever I try to merge 
one into the other, using cg-update from the former branch to the 
latter, if any of these files have been touched, cg-update fails, and I 
have to:

- touch these files in the "old location" manually;
- manually apply the change to the new location (and, sad to say, I 
haven't even figured out how to take the numbers cg-update spits out and 
feed them to cg-diff);
- commit.

Is there any way I can record in the repository that these files are 
actually moved files, and that the merge should apply the patch elsewhere?

Thanks,

	-hpa

Re: Moved files and merges

[Martin Langhoff]

On 9/3/05, H. Peter Anvin <hpa@zytor.com> wrote:
> Is there any way I can record in the repository that these files are
> actually moved files, and that the merge should apply the patch elsewhere?

Well, if you run pickaxe at merge-time on the file-paths that weren't
found, you can probably walk the pickaxe output until you find the
file move, and then reapply the patches.

Probably should be hacked into cg-merge. When the merge reports a file
is missing, what happens? Does it leave a .rej file or anything?

cheers


martin

Re: Moved files and merges

[H. Peter Anvin]

Martin Langhoff wrote:
> 
> Probably should be hacked into cg-merge. When the merge reports a file
> is missing, what happens? Does it leave a .rej file or anything?
> 

The error message is:

MERGE ERROR: nfsmount/mount.c: Not handling case 
3225ecdf8d172cda2a6ea5276af0d3edc566a0e7 ->  -> 
c02da9e576a525a2a49da930107ed3936a45b6e1
MERGE ERROR: nfsmount/sunrpc.c: Not handling case 
037e33e84ebcee4e097a009439c1bab7143ef92d ->  -> 
e2fe5f8b728b5235010ed317e759222179dcd45c

         Conflicts during merge. Do cg-commit after resolving them.

	-hpa

Re: Moved files and merges

[Junio C Hamano]

"H. Peter Anvin" <hpa@zytor.com> writes:

> I currently have two klibc trees,
>
> rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc.git
>
> and
>
> rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc-kbuild.git

I cloned them to take a look.  You_do_ seem to have a lot of
renames.

    $ git clone .../klibc.git klibc
    $ cd klibc
    $ git fetch .../klibc-kbuild.git master:kbuild
    $ git diff -M --diff-filter=R -p kbuild..master |
      git apply --summary --stat

shows that there are 36 files moved around and there are not
that much change overall between them.

Currently merge operation of git does not take any advantage of
the rename/copy detection smarts from git-diff-* family.  So
the short answer to your question is unfortunately no.

Given that they are 'related' trees, and we have proper merge
ancestry information ('git show-branch kbuild master' shows they
were merged two commits before klibc's master branch, and
kbuild's master has 8 or so commits since they last merged), we
should be able to do better.  Let me think about it a bit.

Re: Moved files and merges

[Junio C Hamano]

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

> "H. Peter Anvin" <hpa@zytor.com> writes:
>
>> I currently have two klibc trees,
>
> I cloned them to take a look.  You_do_ seem to have a lot of
> renames.

Well, I think I understand how your trees ancestry looks like,
but still haven't come up with a good problem definition.  I am
sorry that this message is not a solution for your problem but
would end up to be just my rambling and thinking aloud.

The ancestry looks like this:

       ----#4-#5---#7   #0: 1.0.14 released, next version is 1.0.15
      /      /              5691e96ebfccd21a1f75d3518dd55a96b311d1aa
     /---#1-#3---#6     #1: Explain why execvpe/execlpe work the way they do.
    //     /                1d774a8cbd8e8b90759491591987cb509122bd78
  #0-----#2             #2: 1.1 released, next version is 1.1.1
                            3a41b60f6730077db3f04cf2874c96a0e53da453
                        #3: Merge of #2 into #1
                            7ab38d71de2964129cf1d5bc4e071d103e807a0d
                        #4: socketcalls aren't always *.S files; they can...
                            f52be163e684fc3840e557ecf242270926136b67
                        #5: Merge of #3 into #4
                            2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9
                        #6: Warnings cleanup
                            f5260f8737517f19a03ee906cd64dfc9930221cd
                        #7: Remove obsoleted files from merge
                            59709a172ee58c9d529a8c4b6f5cf53460629cb3

and you are trying to merge #6 into #7 (or #7 into #6).  #6 does
not have usr/kinit and nfsmount at the top; #7 has nfsmount
under usr/kinit/.

The merge base of #6 and #7 is #3.  #3->#7 involves many renames
like nfsmount/sunrpc.h -> usr/kinit/nfsmount/sunrpc.h, while
#3->#6 involves no renames.  This can be seen by 

       $ git-diff-tree -M --diff-filter=R -r '#3' '#7' | wc -l

These renames are introduced by #5 merge, whose immediate
ancestors are #3 and #4.

Now, there is a question.  When you merge #6 and #7, development
between #3 and #7 have a lot of renames, while #3 and #6 do not.
What should this merge do?  Should it follow the rename, and if
so why?

Maybe I am trying to solve a wrong problem.  First I thought
there should be an automated way for merge to tell whether
renames done in one branch should be ignored, but that may be
better left under human control.  By looking at #6, #7 and #3
alone, even with looking at #5 which introduced the renames, I
do not see a good reason for the merge machinery to dictate that
these renames are to be followed or ignored when merging #6 and
#7.

So this is not what we ordinary call a 'merge', but what really
is happening is something else .  Let's say the tree you would
want to end up with is 'similar' to #6 but contains the changes
done on the branch leading to #7, except #7 has renames unwanted
for moving #6 forward.  Is that what we should be solving?

Then, I think we could do something along these lines, perhaps?

 - Ask git-diff-tree about changes betwen #3 (merge-base) and
   #7.

        git-diff-tree -M --diff-filter=R -r '#3' '#7' |
        sed -e 's/^[^	]*	//' >.rename-tmp

   This will give us list of <old-name> <new-name>, one pair on
   each line, separated with tabs.

 - check out '#7', and move files around reversing the rename we
   found in the previous step.  Make a throw-away tree out of it;
   we do not even have to have a commit.

        git checkout -b junk7 '#7'
        while read name3 name7
        do
	    test -f $name7 || { echo $name7; continue; }
	    git rename $name7 $name3
        done <.rename-tmp
	tree7_sans_rename=$(git-write-tree)
	git reset --hard junk7

 - check out '#6', and run three-way merge like this.

	git checkout -b junk6 '#6'
        git-read-tree -m -u '#3' '#6' $tree7_sans_rename

 - Notice I did not run merge-cache above.  I suspect that #6
   and #7 just have overlaps but there may be a lot of things
   missing from #7 that you would rather keep (I am not familiar
   with the relationship between these two projects, so I am
   just guessing).  First let's see what is in the tree:

    $ git-ls-files --unmerged
    100644 450e5c7f5c4f4c90df8f60fc98b96cb7db25a502 1       MCONFIG
    100644 450e5c7f5c4f4c90df8f60fc98b96cb7db25a502 2       MCONFIG
    100644 41fdd07af8c4e3eebbafcc3ced8b361882fe4c0d 1       MRULES
    100644 41fdd07af8c4e3eebbafcc3ced8b361882fe4c0d 2       MRULES
    100644 521bf99c2ab1f647156bf16a7f977e951fb9cdb0 1       ash/Makefile
    100644 521bf99c2ab1f647156bf16a7f977e951fb9cdb0 2       ash/Makefile
    100644 66ba9bb16f8289dc8c1af7d1cd49e5f563b5f624 1       gzip/MCONFIG
    100644 66ba9bb16f8289dc8c1af7d1cd49e5f563b5f624 2       gzip/MCONFIG
    100644 d5f9f94be0795accd8b02e2743ab899ac7ca661e 1       gzip/Makefile
    100644 d5f9f94be0795accd8b02e2743ab899ac7ca661e 2       gzip/Makefile
    100644 472f09205986fd9c2f9c7da6e31b45cebb9fe0af 1       ipconfig/MCONFIG
    ...

   Stage 1 is from #3, 2 is from #6, and these files does not
   exist in the faked sans-rename version of #7.  I presume that
   you would want to keep them in #6, so we keep them without
   letting git-merge-cache to remove them by:

	git-ls-files --unmerged | cut -f2 | uniq |
        xargs git-update-cache --

   This still may be slurping a lot of files that only exist in
   #7 but not in #6 in your cache (for example, I suspect you do
   not want to slurp usr/kinit/ into #6 with this 'merge').  You
   may need to remove them, using 'rm -f <file> &&
   git-update-cache --remove <file>'.

 - Then we merge-cache as usual.

	git-merge-cache -o git-merge-one-file-script -a
                      

Re: Moved files and merges

[Fredrik Kuivinen]

On Sat, Sep 03, 2005 at 01:25:50AM -0700, Junio C Hamano wrote:
> Junio C Hamano <junkio@cox.net> writes:
> 
> > "H. Peter Anvin" <hpa@zytor.com> writes:
> >
> >> I currently have two klibc trees,
> >
> > I cloned them to take a look.  You_do_ seem to have a lot of
> > renames.
> 
> Well, I think I understand how your trees ancestry looks like,
> but still haven't come up with a good problem definition.  I am
> sorry that this message is not a solution for your problem but
> would end up to be just my rambling and thinking aloud.
> 
> The ancestry looks like this:
> 
>        ----#4-#5---#7   #0: 1.0.14 released, next version is 1.0.15
>       /      /              5691e96ebfccd21a1f75d3518dd55a96b311d1aa
>      /---#1-#3---#6     #1: Explain why execvpe/execlpe work the way they do.
>     //     /                1d774a8cbd8e8b90759491591987cb509122bd78
>   #0-----#2             #2: 1.1 released, next version is 1.1.1
>                             3a41b60f6730077db3f04cf2874c96a0e53da453
>                         #3: Merge of #2 into #1
>                             7ab38d71de2964129cf1d5bc4e071d103e807a0d
>                         #4: socketcalls aren't always *.S files; they can...
>                             f52be163e684fc3840e557ecf242270926136b67
>                         #5: Merge of #3 into #4
>                             2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9
>                         #6: Warnings cleanup
>                             f5260f8737517f19a03ee906cd64dfc9930221cd
>                         #7: Remove obsoleted files from merge
>                             59709a172ee58c9d529a8c4b6f5cf53460629cb3
> 
> and you are trying to merge #6 into #7 (or #7 into #6).  #6 does
> not have usr/kinit and nfsmount at the top; #7 has nfsmount
> under usr/kinit/.
> 
> The merge base of #6 and #7 is #3.  #3->#7 involves many renames
> like nfsmount/sunrpc.h -> usr/kinit/nfsmount/sunrpc.h, while
> #3->#6 involves no renames.  This can be seen by 
> 
>        $ git-diff-tree -M --diff-filter=R -r '#3' '#7' | wc -l
> 
> These renames are introduced by #5 merge, whose immediate
> ancestors are #3 and #4.
> 
> Now, there is a question.  When you merge #6 and #7, development
> between #3 and #7 have a lot of renames, while #3 and #6 do not.
> What should this merge do?  Should it follow the rename, and if
> so why?
> 

Maybe I am missing something... but why should the merge operation
ignore renames? Is there a merge case when ignoring renames is the
Right Thing to do?

Lets say the branches A and B has the common ancestor C which contains
a file named "foo". If A has renamed "foo" to "foobar" and B has made
some content changes to "foo" shouldn't the result be a file named
"foobar" with the content changes B made to "foo" in it?

As I see it when we rename 'foo' to 'foobar' we say that "this file
should from now on be named 'foobar'". Furthermore, when we make some
content changes to some file we say "this file should have this new
content instead of its old content". In particular I do not think the
user expresses an intent to keep the name of a file just because she
makes some changes to its contents. So IMHO the merge of "this file
should from now on be named 'foobar'" and "this file should have this
new content instead of its old content" should be "this file should
from now on be named 'foobar' and have this new content".

I think it is feasible to teach the merge machinery about those rename
cases, it probably isn't trivial to implement but I certainly think it
is possible. It may be the case that the user should be warned when
such automatic merges involving renames are performed though.


- Fredrik

Re: Moved files and merges

[Junio C Hamano]

Fredrik Kuivinen <freku045@student.liu.se> writes:

> Maybe I am missing something... but why should the merge operation
> ignore renames? Is there a merge case when ignoring renames is the
> Right Thing to do?
>
> Lets say the branches A and B has the common ancestor C which contains
> a file named "foo". If A has renamed "foo" to "foobar" and B has made
> some content changes to "foo" shouldn't the result be a file named
> "foobar" with the content changes B made to "foo" in it?

Our messages mostly crossed, but as I described in the longer
message I just sent out, the problem is that two lines of
development runs in parallel, each of them wants to pick
criss-cross nonstructural changes from the other, while keeping
their own tree structure.  If the goal of a 'merge' is to
converge into a single commit for both lines of development to
agree on a single tree structure to carry on from, then what you
said is right, but the problem at hand is slightly different.

Re: Moved files and merges

[Junio C Hamano]

This is a simplified scenario of klibc vs klibc-kbuild HPA had
trouble with, to help us think of a way to solve this
interesting merge problem.

	 #1 - #3 - #5 - #7
       /    /         /
    #0 - #2 - #4 - #6

There are two lines of developments.  #0->#2 renames F to G and
introduces K.  #0->#1 keeps F as F and does not introduce K.

At commit #3, #2 is merged into #1.  The changes made to the
file contents of F between #0 and #2 are appreciated, but the
renaming of F to G and introduction of K were not.  So commit #3
has the resulting merge contents in F and does not have file K.
This _might_ be different from what we traditionally consider a
'merge', but from the use case point of view it is a valid thing
one would want to do.

Commit #4 is a continued development from #2; changes are made
to G, and K has further changes.  Commit #5 similarly is a
continued development from #3; its changes are in F and K does
not exist.

We are about to merge #6 into #5 to create #7.  We should be
able to take advantage of what the user did when the merge #3
was made; namely, we should be able to infer that the line of
development that flows #0 .. #3 .. #7 prefers to keep F as F,
and does not want the newly introduced K.  We should be able to
tell it by looking at what the merge #3 did.

Now, how can we use git to figure that out?

First, given our current head (#5) and the other head we are
about to merge (#6), we need a way to tell if we merged from
them before (i.e. the existence of #3) and if so the latest of
such merge (i.e. #3).

The merge base between #5 and #6 is #2.  We can look at commits
between us (#5) and the merge base (#2), find a merge (#3),
which has two parents.  One of the parents is #2 which is
reachable from #6, and the other is #1 which is not reachable
from #6 but is reachable from #5.  Can we say that this reliably
tells us that #2 is on their side and #1 is on our side?  Does
the fact that #3 is the commit topologically closest to #5 tell
us that #3 is the one we want to look deeper?

This is still handwaving, but assuming the answers to these
questions are yes, we have found that the 'previous' merge is
#3, that #1 is its parent on our side, and that #2 is its parent
on their side.

Then we can ask 'diff-tree -M #2 #3' to see what `tree
structure` changes we do _not_ want from their line of
development, while slurping the contents changes from them.
When making the tree to put at #7, just like I outlined to my
previous message to HPA, we can first create a tree that is a
derivative of #6 with only the structural changes detected
between #2 and #3 (which are 'rename from G to F' and 'removal
of K') applied.  Similarly, we make another derivative, this
time of #2, with only the structural changes to adjust it to
'our' tree (again, 'rename from G to F' and 'removal of K').
Then we can run 3-way git-read-tree like this:

    git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'

The last part, using the structurally adjusted tree as the
merge-base tree, is what I forgot to do in the previous message
to HPA.

Hmm.

Re: Moved files and merges

[Sam Ravnborg]

On Sat, Sep 03, 2005 at 11:46:53AM -0700, Junio C Hamano wrote:
> This is a simplified scenario of klibc vs klibc-kbuild HPA had
> trouble with, to help us think of a way to solve this
> interesting merge problem.
> 
> 	 #1 - #3 - #5 - #7
>        /    /         /
>     #0 - #2 - #4 - #6
> 
> There are two lines of developments.  #0->#2 renames F to G and
> introduces K.  #0->#1 keeps F as F and does not introduce K.

As explained in another mail what we want to do is actually to
transpose the changes made to F to the now renamed file G.
So we end up with G containing the modifications made to F.

Also we want to include the new file K.

So we end up with a new commit containing the renamed file with
modifications and the new files too.

I hope this simplfies the usecase from a git perspective.

	Sam

Re: Moved files and merges

[Junio C Hamano]

Sam Ravnborg <sam@ravnborg.org> writes:

> As explained in another mail what we want to do is actually to
> transpose the changes made to F to the now renamed file G.
> So we end up with G containing the modifications made to F.
>
> Also we want to include the new file K.

Thanks for the clarification.  But the principles are the same.

Re: Moved files and merges

[Sam Ravnborg]

On Sat, Sep 03, 2005 at 12:32:03PM -0700, Junio C Hamano wrote:
> Sam Ravnborg <sam@ravnborg.org> writes:
> 
> > As explained in another mail what we want to do is actually to
> > transpose the changes made to F to the now renamed file G.
> > So we end up with G containing the modifications made to F.
> >
> > Also we want to include the new file K.
> 
> Thanks for the clarification.  But the principles are the same.

Not the way I read your explanation.

Lets try to cook up an example:

Common ancestor looks like this:
foo/foo.c

Then we have two lines of parallel development
dev-line-0 modifes foo/foo.c
dev-line-1 moves foo/foo.c to bar/bar.c
In addition dev-line-1 adds a second file bar/Makefile

So what should happen when we merge the two dev-lines?
The resulting tree should look like this:
bar/bar.c (including the modifications down in dev-line-1 to foo.c
bar/Makefile as added in dev-line-2

If this fits into your longer description - then yes this is the same
principle. But I failed to see it fit, therefore this simple example.

If the problem is not fully understood it can be difficult to come up
with the proper solution. And with the example above the problem should
be really easy to understand.
Then we have the tree as used by hpa with a few more mergers in it. But
the above is what was initial tried to do with the added complexity of a
few more renames etc.

	Sam

Re: Moved files and merges

[Junio C Hamano]

Sam Ravnborg <sam@ravnborg.org> writes:

> If the problem is not fully understood it can be difficult to come up
> with the proper solution. And with the example above the problem should
> be really easy to understand.
> Then we have the tree as used by hpa with a few more mergers in it. But
> the above is what was initial tried to do with the added complexity of a
> few more renames etc.

All true.  Let's redraw that simplified scenario, and see if
what I said still holds.  It may be interesting to store my
previous message and this one and run diff between them.  I
suspect that the main difference to come out would be the the
problem description part and the merge machinery part would not
be all that different.

------------
This is a simplified scenario of klibc vs klibc-kbuild HPA had
trouble with, to help us think of a way to solve this
interesting merge problem.

	 #1 - #3 - #5 - #7
       /    /         /
    #0 - #2 - #4 - #6

There are two lines of developments.  #0->#1 renames F to G and
introduces K.  #0->#2 keeps F as F and does not introduce K.

At commit #3, #2 is merged into #1.  The changes made to the
file contents of F between #0 and #2 are appreciated, but we
would also want to keep our decision to rename F to G and our
new file K.  So commit #3 has the resulting merge contents in G
and has K, inherited from #1.  This _might_ be different from
what we traditionally consider a 'merge', but from the use case
point of view it is a valid thing one would want to do.

I handwaved in my original message, but resolving this merge is
not something git can help you mechanically; obviously it cannot
decide if you want to keep the rename for you.

Commit #4 is a continued development from #2; changes are made
to F, and there is no K.  Commit #5 similarly is a continued
development from #3; its changes are made to G and K also has
further changes.

We are about to merge #6 into #5 to create #7.  We should be
able to take advantage of what the user did when the merge #3
was made; namely, we should be able to infer that the line of
development that flows #0 .. #3 .. #7 prefers to rename F to G,
and also wants the newly introduced K.  We should be able to
tell it by looking at what the merge #3 did.

Now, how can we use git to figure that out?

First, given our current head (#5) and the other head we are
about to merge (#6), we need a way to tell if we merged from
them before (i.e. the existence of #3) and if so the latest of
such merge (i.e. #3).

The merge base between #5 and #6 is #2.  We can look at commits
between us (#5) and the merge base (#2), find a merge (#3),
which has two parents.  One of the parents is #2 which is
reachable from #6, and the other is #1 which is not reachable
from #6 but is reachable from #5.  Can we say that this reliably
tells us that #2 is on their side and #1 is on our side?  Does
the fact that #3 is the commit topologically closest to #5 tell
us that #3 is the one we want to look deeper?

This is still handwaving, but assuming the answers to these
questions are yes, we have found that the 'previous' merge is
#3, that #1 is its parent on our side, and that #2 is its parent
on their side.

Then we can ask 'diff-tree -M #2 #3' to see what `tree
structure` non-changes we do _not_ want from their line of
development, while slurping the contents changes from them.
When making the tree to put at #7, just like I outlined to my
previous message to HPA, we can first create a tree that is a
derivative of #6 with only the structural changes detected
between #2 and #3 (which are 'rename from F to G' and 'addition
of K') applied.  Here, applying 'addition of K' is only
conceptual, unlike the original message you (Sam) had trouble
with due to my misunderstanding of which line of development
renames/adds.  It is conceptual in the sense that we do not have
to do anything special.  #6-adjusted is different from #6 in
that it has F's contents from #6 at G.

Similarly, we make another derivative, this time of #2, with
only the structural changes to adjust it to 'our' tree (again,
'rename from F to G' and 'addition of K' which is only
conceptual --- that is, #2-adjusted has contents of F from #2 at
G).  Then we can run 3-way git-read-tree like this:

    git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'

The last part, using the structurally adjusted tree as the
merge-base tree, is what I forgot to do in the previous message
to HPA.

In all these three trees fed to read-tree, the original F
(modified in two lines since #0 which had it at F) appears at F,
so the normal 3-way merge machinery would work just fine.  #2
does not have G (neither #2-adjusted), #5 does, and #6 does not
(neither #6-adjusted), so again the ordinary 3-way merge
machinery would pick up G from #5 and drop it in #7.  That's why
'adjusting to our tree' for addition is only conceptual, unlike
the removal and rename in the previous message.

So as I said, the principle is not that different.

Any volunteer to code this up and see how well it works in
practice?

Re: Moved files and merges

[Daniel Barkalow]

On Sun, 4 Sep 2005, Junio C Hamano wrote:

> Sam Ravnborg <sam@ravnborg.org> writes:
> 
> > If the problem is not fully understood it can be difficult to come up
> > with the proper solution. And with the example above the problem should
> > be really easy to understand.
> > Then we have the tree as used by hpa with a few more mergers in it. But
> > the above is what was initial tried to do with the added complexity of a
> > few more renames etc.
> 
> All true.  Let's redraw that simplified scenario, and see if
> what I said still holds.  It may be interesting to store my
> previous message and this one and run diff between them.  I
> suspect that the main difference to come out would be the the
> problem description part and the merge machinery part would not
> be all that different.

I'm not quite so convinced, because I think that the actual situation is a 
bit more natural, and therefore our expectations at the end should be 
closer to right with less attention to detail. But I think the actual 
situation is more interesting, anyway, because it's more likely to happen 
and we're more likely to be able to help.

> ------------
> This is a simplified scenario of klibc vs klibc-kbuild HPA had
> trouble with, to help us think of a way to solve this
> interesting merge problem.
> 
> 	 #1 - #3 - #5 - #7
>        /    /         /
>     #0 - #2 - #4 - #6
> 
> There are two lines of developments.  #0->#1 renames F to G and
> introduces K.  #0->#2 keeps F as F and does not introduce K.
> 
> At commit #3, #2 is merged into #1.  The changes made to the
> file contents of F between #0 and #2 are appreciated, but we
> would also want to keep our decision to rename F to G and our
> new file K.  So commit #3 has the resulting merge contents in G
> and has K, inherited from #1.  This _might_ be different from
> what we traditionally consider a 'merge', but from the use case
> point of view it is a valid thing one would want to do.

I think this is actually quite a regular merge, and I think we should be 
able to offer some assistance. The situation with K is normal: case #3ALT. 
If someone introduces a file and there's no file or directory with that 
name in other trees, we assume that the merge should include it.

F/G is trickier, and I don't think we can actually do much about it with 
the current structure of read-tree/merge-cache/etc, but, theoretically, we 
should recognize that #0->#1 is a rename plus content changes, and #0->#2 
is content changes, so the total should be the rename plus contents 
changes; I think we want to additionally signal a conflict, because 
there's a reasonable chance that the rename will interfere with the #0->#2 
changes, and need intervention. Most likely, this just means that we 
should not commit automatically, but have the user test the result first.

For now, of course, we don't get renames at any point in the merging 
procedure, so our code can't tell, and sees it as a big conflict that the 
user has to deal with. But we can agree on what the result is if the user 
"includes all the changes from the other branch" (and see the situation 
you reported first as "cherry-picking" the content and leaving the 
structural changes).

> Commit #4 is a continued development from #2; changes are made
> to F, and there is no K.  Commit #5 similarly is a continued
> development from #3; its changes are made to G and K also has
> further changes.
> 
> We are about to merge #6 into #5 to create #7.  We should be
> able to take advantage of what the user did when the merge #3
> was made; namely, we should be able to infer that the line of
> development that flows #0 .. #3 .. #7 prefers to rename F to G,
> and also wants the newly introduced K.  We should be able to
> tell it by looking at what the merge #3 did.

Again, K should be unexceptional, because we're keeping a file that was 
added to one side but not the other. (In the other situation, it still 
works; relative to the common ancestor, we're in #8ALT, since #5 doesn't 
have K, which was in #2 and #6; we see the rejection in a merge as a 
removal, which is effectively the same.)

> Now, how can we use git to figure that out?

First off, it should handle K automatically, because we're still including 
a file added by one side without interference from the other side.

> First, given our current head (#5) and the other head we are
> about to merge (#6), we need a way to tell if we merged from
> them before (i.e. the existence of #3) and if so the latest of
> such merge (i.e. #3).
> 
> The merge base between #5 and #6 is #2.  We can look at commits
> between us (#5) and the merge base (#2), find a merge (#3),
> which has two parents.  One of the parents is #2 which is
> reachable from #6, and the other is #1 which is not reachable
> from #6 but is reachable from #5.  Can we say that this reliably
> tells us that #2 is on their side and #1 is on our side?  Does
> the fact that #3 is the commit topologically closest to #5 tell
> us that #3 is the one we want to look deeper?
> 
> This is still handwaving, but assuming the answers to these
> questions are yes, we have found that the 'previous' merge is
> #3, that #1 is its parent on our side, and that #2 is its parent
> on their side.
> 
> Then we can ask 'diff-tree -M #2 #3' to see what `tree
> structure` non-changes we do _not_ want from their line of
> development, while slurping the contents changes from them.
> When making the tree to put at #7, just like I outlined to my
> previous message to HPA, we can first create a tree that is a
> derivative of #6 with only the structural changes detected
> between #2 and #3 (which are 'rename from F to G' and 'addition
> of K') applied.  Here, applying 'addition of K' is only
> conceptual, unlike the original message you (Sam) had trouble
> with due to my misunderstanding of which line of development
> renames/adds.  It is conceptual in the sense that we do not have
> to do anything special.  #6-adjusted is different from #6 in
> that it has F's contents from #6 at G.

That's true, but we don't need to find and use #3; we can just use #5. The 
only difference is structural changes introduced between #3 and #5, and we 
presume we want those changes as well, unless they conflict with 
something. And if we don't look for #3, we can recognize the merge of #0, 
#1, and #2 as the same situation, with the same solution.

> Similarly, we make another derivative, this time of #2, with
> only the structural changes to adjust it to 'our' tree (again,
> 'rename from F to G' and 'addition of K' which is only
> conceptual --- that is, #2-adjusted has contents of F from #2 at
> G).  Then we can run 3-way git-read-tree like this:
> 
>     git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'
> 
> The last part, using the structurally adjusted tree as the
> merge-base tree, is what I forgot to do in the previous message
> to HPA.
> 
> In all these three trees fed to read-tree, the original F
> (modified in two lines since #0 which had it at F) appears at F,
> so the normal 3-way merge machinery would work just fine.  #2
> does not have G (neither #2-adjusted), #5 does, and #6 does not
> (neither #6-adjusted), so again the ordinary 3-way merge
> machinery would pick up G from #5 and drop it in #7.  That's why
> 'adjusting to our tree' for addition is only conceptual, unlike
> the removal and rename in the previous message.
> 
> So as I said, the principle is not that different.

We already do the addition and non-addition (like removal) in read-tree. 
We could also handle renames there as well, although I can't quite picture 
an efficient code organization for it. Of course, read-tree is in flux at 
the moment, so making more structural changes to it at the same time is 
awkward.

In any case, I think that your algorithm is correct, except that you can 
use the sides of the present merge and the common ancestor, rather than 
looking for past merges, which aren't really relevant. (For that matter, 
there's no reason to believe that #1 and #5 are "part of the same line"; 
you'd get the same graph if #3 were merging some third party's 
restructuring, and 4 and 6 were a fork that started before the change and 
is being merged after it:

  1
 / \
0-2-3-5-7
   \   /
    4-6

It shouldn't matter to the merge at 7 if the 2-3 reorganization was done 
locally, by applying a patch, or by merging.

	-Daniel
*This .sig left intentionally blank*

Re: Moved files and merges

[Junio C Hamano]

Daniel Barkalow <barkalow@iabervon.org> writes:

> I think this is actually quite a regular merge, and I think we should be 
> able to offer some assistance. The situation with K is normal: case #3ALT. 
> If someone introduces a file and there's no file or directory with that 
> name in other trees, we assume that the merge should include it.

I was not particularly interested in discussing the initial
merge, which is a perfectly regular merge as you said.  I was
more focusing on reusing the tree-structure change information
we _could_ find in merge #3 when we make later merges, because
that merge is something the user did in the past and would be a
good guide for guessing what the user wants to happen to this
round.

There is no question about K in 'keeping addition' case.  It
gets interesting only when the first merge prefered 'reject
addition by them' and we would want to reuse that preference in
the second merge.  But as I tried to clarify in the "a couple of
things worth mentioning" message, there is no fundamental reason
to treat removal and addition any differently.  It is just a way
to reduce unnecessary conflicts.

> Most likely, this just means that we 
> should not commit automatically, but have the user test the result first.

No question about it again.

> Of course, read-tree is in flux at 
> the moment, so making more structural changes to it at the same time is 
> awkward.

Doing this in read-tree is a bit premature.  I'd prefer a
scripted solution first to see what we want and how well it
works in practice.

>   1
>  / \
> 0-2-3-5-7
>    \   /
>     4-6
>
> It shouldn't matter to the merge at 7 if the 2-3 reorganization was done 
> locally, by applying a patch, or by merging.

There was another problem in my message that treated #3
specially.  I did it that way primarily because I wanted to have
an algorithm that needs to look only limited (namely, one)
number of commits, more than what we currently look at.  The
problem is that the trail #0..#1..#3 (in the example in second
message, whose rename probably happened between #0 and #1) may
change the contents of the renamed file so drastically that diff
between #2 and #3 may not look like rename anymore, while we
could still detect it if we followed the whole trail and looked
for renames between each commit on it.

Re: Moved files and merges

[H. Peter Anvin]

Junio C Hamano wrote:
> 
>>  1
>> / \
>>0-2-3-5-7
>>   \   /
>>    4-6
>>
>>It shouldn't matter to the merge at 7 if the 2-3 reorganization was done 
>>locally, by applying a patch, or by merging.
> 
> 
> There was another problem in my message that treated #3
> specially.  I did it that way primarily because I wanted to have
> an algorithm that needs to look only limited (namely, one)
> number of commits, more than what we currently look at.  The
> problem is that the trail #0..#1..#3 (in the example in second
> message, whose rename probably happened between #0 and #1) may
> change the contents of the renamed file so drastically that diff
> between #2 and #3 may not look like rename anymore, while we
> could still detect it if we followed the whole trail and looked
> for renames between each commit on it.
> 

One question, of course, is if one should simply keep additional 
metadata around to handle this sort of situations.  One could, for 
example, keep a UUID for each file, which would be carried over by the 
renaming commit.  If one runs into a tree which doesn't have the UUIDs, 
they should be generated at that time (this could be a bit tricky to do 
without invalidating all signatures in the tree, since the obvious way 
-- adding it to the tree object -- would invalidate all the commit and 
tag objects.)

In some ways this is similar to the Unix filesystem model of separating 
location (pathname) from identity (device:inode).

It would also hade the somewhat interesting possibility that one could 
"remove and recreate" a file and have it exist as a different entity. 
That probably needs to be a user option.

	-hpa

Re: Moved files and merges

[Linus Torvalds]

On Mon, 5 Sep 2005, H. Peter Anvin wrote:
> 
> It would also hade the somewhat interesting possibility that one could 
> "remove and recreate" a file and have it exist as a different entity. 
> That probably needs to be a user option.

It's a totally broken model. Really.

You think it solves issues, but it just creates more bugs and problems 
than it solves.

Trust me. The whole point of git is that "content is the only thing that 
matters", and that there isn't any other meta-data. If you break that 
fundamental assumption, everything git does so well will break. 

I think we've already shown that the "content matters" approach works.  I
claim that the git rename tracking works better than any other SCM out 
there, _exactly_ because it doesn't make the mistake of trying to track 
anything but content.

The "moved + modified files" is not anything special. The current 
automatic merger may not handle it, but that's not because it _can't_ 
handle it, it's because it tries to be simple and efficient. 

And because it's so _incredibly_ fast for all the normal cases, you can 
now spend some effort on figuring out renames dynamically for the few 
cases where it fails. Does it do so now? No. Would adding UUID's help? 
Hell no. It would be just an unmitigated disaster.

Exactly the same way "git-diff-tree" can figure out renames, a merge 
algorithm can figure them out. 

Right now, we have two stages in merges: we try the trivial merge first
(pure "git-read-tree"), and when that fails, we try the automatic 3-way
merge. The fact that we don't have a third (and fourth, and fifth) merge
algorithm for when those two trivial merges happen to not work is _not_ an
indication that the "contents only" approach doesn't work - it's just an
indication of the fact that 99.9% of all merges are trivial, and they
should be optimized for.

So the next step is _not_ to do UUID's, it's to notice that merge errors 
happened, and try to figure out why. Right now we just give up and say 
"sort it out by hand". That's actually a perfectly valid approach even in 
the presense of moved files - it's a bit painful, but once you _do_ sort 
it out and commit the merge, especially if you can push the merge back (so 
that both sides then agree on the final rename), future merges will be 
trivial again - ie you won't have to go through it over and over again.

Of course, if you don't push it back, but keep the two trees separate and 
keep on modifying files that have different names in the other repository, 
you'll keep on getting into the situation that the trivial merge doesn't 
work. So we _do_ want to get an automated "phase 3" (and maybe 4..) merge 
that can figure out renames, but the point here is that it's something we 
_can_ figure out.

For example, one way of doing it is to just do the exact merge we do now,
and then look at the files that didn't merge. Do a cross-diff between such
files and new/deleted files (if not _exactly_ the way we do for "git diff
-M", then at least it's exactly the same concept), and try to do a
three-way merge where the base/first/second pairs don't have the same
name.

For example, let's say that you have the common commit A, and file "x",
and two paths (B and C) where B has renamed the file "x" to "y", and C has
modified file "x". You end up with the schenario that our trivial merge
fails to handle, and right now we give up, and don't help the user very
much at all. But the _solution_ is not to change "read-tree" to know about
renames, nor is it to make git keep any new data. The solution is to just 
make phase 3 say:

 - "Automatic merge failed, trying rename merge"
 - go through all files that exist in C but not in B (or vice versa), and 
   pair them up with all files that exist in B but not in C (or vice
   versa) and see if _they_ can be handled as a three-way merge. And 
   exactly the same way that we do the rename detection, we may want to
   find the "optimal pairing" by looking at the distance between the
   files.

Notice? This will automatically handle the "renamed in one branch, 
modified in another" case. In fact, if the renamer modified it too, that's 
not a problem at all - the three-way merge will work exactly the same way 
it does now with the case of a non-moved "modified in both" files.

Problem solved. Without complicating the trivial (and very common) cases, 
and without introducing any new metadata that is fundamentally impossible 
to maintain (and it _is_ fundamentally impossible to maintain, because it 
has nothing to do with the contents of the files, so patches etc will by 
definition break it).

		Linus

Re: Moved files and merges

[H. Peter Anvin]

Linus Torvalds wrote:
> 
> It's a totally broken model. Really.
> 
> You think it solves issues, but it just creates more bugs and problems 
> than it solves.
> 
> Trust me. The whole point of git is that "content is the only thing that 
> matters", and that there isn't any other meta-data. If you break that 
> fundamental assumption, everything git does so well will break. 
> 
> I think we've already shown that the "content matters" approach works.  I
> claim that the git rename tracking works better than any other SCM out 
> there, _exactly_ because it doesn't make the mistake of trying to track 
> anything but content.
> 
> The "moved + modified files" is not anything special. The current 
> automatic merger may not handle it, but that's not because it _can't_ 
> handle it, it's because it tries to be simple and efficient. 
> 
> And because it's so _incredibly_ fast for all the normal cases, you can 
> now spend some effort on figuring out renames dynamically for the few 
> cases where it fails. Does it do so now? No. Would adding UUID's help? 
> Hell no. It would be just an unmitigated disaster.
> 

Okay, how about keeping a cache (derived from the contents) of these 
types of data, to assist the merge if necessary?  If it doesn't exist 
when needed, it can just be created, which may take O(n) time.

	-hpa

Re: Moved files and merges

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Of course, if you don't push it back, but keep the two trees separate and 
> keep on modifying files that have different names in the other repository, 
> you'll keep on getting into the situation that the trivial merge doesn't 
> work. So we _do_ want to get an automated "phase 3" (and maybe 4..) merge 
> that can figure out renames, but the point here is that it's something we 
> _can_ figure out.

Thanks.  You very well said exactly what I should have said; I
failed to explain where that `reusing rename information from
previous merge` algorithm should fit in the bigger picture.

And the algorithm you describe (and Daniel briefly outlined) is
slightly different from what I had in mind in that it does not
have to depend on previous merge, which is also nice.

Re: Moved files and merges

[Junio C Hamano]

"H. Peter Anvin" <hpa@zytor.com> writes:

> One question, of course, is if one should simply keep additional 
> metadata around to handle this sort of situations.  One could, for 
> example, keep a UUID for each file,...

If I am not mistaken, that is exactly what tla does.  It seems
to work well in practice and seem so simple (at least
superficially, I have not looked deeply into the issues involved
in keeping it sync with the contents and how to recover if the
user ever screws up, etc.), and I can see why people find it so
attractive.  I myself once did.

But previous argument by Linus made in a distant (in git
timescale) past is now ingrained in my brain: "the additional
metadata" recorded at the commit time can only help us what we
envisioned in the past when the tool to record that metadata was
written.  If we try to "track" by contents, we can do at least
the same (diff -M being able to tell renames is an example that
we can get away without having a UUID) and possibly better,
depending on how much effort we are willing to spend "drilling
down" when we actually need to know what happened at merge
time.  What I found most important in that argument by Linus is
that the "drilling down" algorithm can improve over time while
"the additional metadata" specification is cast in stone when a
commit is made.

Re: Moved files and merges

[H. Peter Anvin]

Junio C Hamano wrote:
> 
> But previous argument by Linus made in a distant (in git
> timescale) past is now ingrained in my brain: "the additional
> metadata" recorded at the commit time can only help us what we
> envisioned in the past when the tool to record that metadata was
> written.  If we try to "track" by contents, we can do at least
> the same (diff -M being able to tell renames is an example that
> we can get away without having a UUID) and possibly better,
> depending on how much effort we are willing to spend "drilling
> down" when we actually need to know what happened at merge
> time.  What I found most important in that argument by Linus is
> that the "drilling down" algorithm can improve over time while
> "the additional metadata" specification is cast in stone when a
> commit is made.
> 

... unless the "additional metadata" is merely a cache, derived from the 
contents.  The advantage, of course, is that you can produce data that 
is more expensive that way.  On the other hand, if you don't need it, 
it's pointless.

	-hpa

Re: Moved files and merges

[Junio C Hamano]

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

> All true.  Let's redraw that simplified scenario, and see if
> what I said still holds.  It may be interesting to store my
> previous message and this one in a file and run diff between
> them.

There are a couple of things worth mentioning about the two
examples (one that I resolved favoring non-rename and
non-addition, and the other I resolved favoring rename and
addition) I gave tonight.

1. When I said "the principles are the same", I was primarily
   referring to the part that detects the 'previous' merge,
   which of its parents is 'ours' and which is 'theirs'.
   Although I handwaved that part in both examples, my gut
   feeling is that this part is probably harder than the part
   that adjusts trees before merging.  klibc vs klibc-kbuild
   case had a clear distinction between which commit is ours and
   which is theirs, but I am not sure if things are that black
   and white in real projects when a lot of criss-crossing
   merges are involved.

2. When adjusting trees, I treated removals and additions a bit
   differently, but there is no fundamental reason to do so.

   In the first example which had a removal, I adjusted the tree
   #2 and #6 by removing the path involved.  In the second
   example which had an addition, I did not adjust the tree #2
   and #6 to add that path.  But you _could_ do nothing to
   adjust for removal; i.e. leaving K in tree #2-adjusted and
   #6-adjusted in the first example. Also you _could_ adjust for
   the addition by copying K from #3 into #2-adjusted and
   copying K from #5 into #6-adjusted in the second example.

   If you did the former, merging the resulting #6-adjusted into
   #5 pivoting at #2-adjusted would leave a non-trivial conflict
   for you to resolve by hand.  #6-adjusted changes K from
   #2-adjusted while #5 would remove it from #2-adjusted.  This
   would be a remove-modify conflict (case 7 in the 3-way merge
   case table in t/t1000-read-tree-m-3way.sh).  But this is only
   non-trivial to git and what you want is obvious to you as the
   maintainer of the line of development that removed the file
   at #3.  You removed it the last time, and you remove it this
   time again.  I adjusted #2 and #6 to remove the path only to
   save you from this tedium upfront before the read-tree phase.

   Similarly, in the second example, if #2 and #6 are adjusted
   for the addition of K by copying K from #3 and #5 into them,
   the resulting merge would see that one line #2-adjusted to
   #6-adjusted changes K (whose contents is that of
   #3) to that of #5, while the other line #2-adjusted to #5
   changes K (whose contents is again that of #3) to that of
   #5.  Since this is both-change-identically (case 12 in the
   3-way merge table), it trivially resolves to keep K from #5,
   and the result is the same as what you would get from my
   second example which did nothing about additions.



   

Re: Moved files and merges

[Fredrik Kuivinen]

On Sat, Sep 03, 2005 at 11:46:53AM -0700, Junio C Hamano wrote:
[lots of good stuff]

I obviously misunderstood the complexity of this merge case. Thank you
for the explanation. 

- Fredrik

Re: Moved files and merges

[Sam Ravnborg]

On Sat, Sep 03, 2005 at 01:25:50AM -0700, Junio C Hamano wrote:
> Junio C Hamano <junkio@cox.net> writes:
> 
> > "H. Peter Anvin" <hpa@zytor.com> writes:
> >
> >> I currently have two klibc trees,
> >
> > I cloned them to take a look.  You_do_ seem to have a lot of
> > renames.
> 
> Well, I think I understand how your trees ancestry looks like,
> but still haven't come up with a good problem definition.  I am
> sorry that this message is not a solution for your problem but
> would end up to be just my rambling and thinking aloud.
> 
> The ancestry looks like this:
> 
>        ----#4-#5---#7   #0: 1.0.14 released, next version is 1.0.15
>       /      /              5691e96ebfccd21a1f75d3518dd55a96b311d1aa
>      /---#1-#3---#6     #1: Explain why execvpe/execlpe work the way they do.
>     //     /                1d774a8cbd8e8b90759491591987cb509122bd78
>   #0-----#2             #2: 1.1 released, next version is 1.1.1
>                             3a41b60f6730077db3f04cf2874c96a0e53da453
>                         #3: Merge of #2 into #1
>                             7ab38d71de2964129cf1d5bc4e071d103e807a0d
>                         #4: socketcalls aren't always *.S files; they can...
>                             f52be163e684fc3840e557ecf242270926136b67
>                         #5: Merge of #3 into #4
>                             2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9
>                         #6: Warnings cleanup
>                             f5260f8737517f19a03ee906cd64dfc9930221cd
>                         #7: Remove obsoleted files from merge
>                             59709a172ee58c9d529a8c4b6f5cf53460629cb3
> 
> and you are trying to merge #6 into #7 (or #7 into #6).  #6 does
> not have usr/kinit and nfsmount at the top; #7 has nfsmount
> under usr/kinit/.


Hi Junio.

Ican expalin some of the background for this particular merge.
At about one month ago I cloned the current klibc.git tree and started
doing the necessary modifications needed to introduce kbuild - the
build system used in the kernel.
Futhermore we decided to move files around so they fit the directory
structure planned to be used in the kernel - when we at one point in the
future merged with mainline.
While I were modifying the build system the development continued and a
few files saw some updates in the official klibc tree.

So what we want to do in this case is:
- Merge the kbuild changes into the official tree without loosing the
  changes made to renamed files.

On purpose I did not modify any of the renamed files so the klibc-kbuild
tree contains renames only for these.

If it would be possible to merge:
libs/klibc/klibc.git and libs/klibc/sam/klibc-kbuild.git
using the above rules it would be perfect.

Then a few of the patches from libs/klibc/klibc-kbuild.git would have to
be applied again, but thats doable.

Anyway my view on it. Since Peter is the one doing the merge he may have
better ideas.

	Sam