overly smart rebase - bug or feature?

overly smart rebase - bug or feature?

[Fedor Sergeev]

Folks,

I have recently hit a behavior which might well be a feature, 
but it was very surprising (in a bad sense) to me.

I was trying to rebase a branch with changes in some file onto a branch
where this file was recently deleted. I would expect rebase to fail and 
suggest me to  resolve conflict manually.
However it somehow succeeded managing to find another file to patch instead 
of the initial one:

] cat git-rebase-bug.sh
#!/bin/sh
git init
# create three files with the same contents
perl -e ' for ($i=0; $i < 10; $i++) { print "$i\n" } ' >Makefile
cp Makefile Makefile1
cp Makefile Makefile2
git add .
git commit -m"created 3 makefiles"
# delete one file
git rm Makefile
git commit -m"deleted 1 makefile"
# go to another branch, one step back
git checkout -b mod HEAD^
# modify contents of the file deleted in master branch
echo "#10" >>Makefile
git add -u
git commit -m"modified 1 makefile"
# now rebase "mod" on top of "master" not expecting it to succeed
git rebase master mod
]

] mkdir git-bug; cd git-bug
] ../git-rebase-bug.sh
....
First, rewinding head to replay your work on top of it...
Applying: modified 1 makefile
error: Makefile: does not exist in index
Using index info to reconstruct a base tree...
Falling back to patching base and 3-way merge...
]

Now if I look at the rebase result I see that it chose to patch "Makefile2" 
instead of my lovely "Makefile" (why not Makefile1, btw ;) ):

] git log --stat -1 --pretty=oneline
ce0101fc7884bce3eb9724b75d654e7c40abf0fd modified 1 makefile
 Makefile2 |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)
]

I has always agreed with the claim that simple but reliable merge
(rebase, whatever) is much better than smartass one smarter than yourself.

And, to be honest, both merge and cherry-pick do not try to play smart:

] git reset --hard mod@{1}
] git checkout master
] git merge mod
CCONFLICT (delete/modify): Makefile deleted in HEAD and modified in mod. Version mod of Makefile left in tree.
Automatic merge failed; fix conflicts and then commit the result.
] git reset --hard
] git cherry-pick mod
Automatic cherry-pick failed.  After resolving the conflicts,
mark the corrected paths with 'git add <paths>' or 'git rm <paths>' and commit the result.
When commiting, use the option '-c f782a81' to retain authorship and message.
]

So, why rebase is smarter?

Yeah, and if it matters I tried it on 1.6.0.2 and 1.5.3.8 on Solaris and Linux.

best regards,
  Fedor.
PS I had problems reaching this list, thus ccing Junio explicitly.
I'm not on the list, btw..

Re: overly smart rebase - bug or feature?

[Junio C Hamano]

Fedor Sergeev <Fedor.Sergeev@Sun.COM> writes:

> I have recently hit a behavior which might well be a feature, 
> but it was very surprising (in a bad sense) to me.

It is a feature misfiring.

Rebase is essentially a repeated cherry-pick, and a cherry-pick of commit
A on top of commit B is done by a simplified 3-way merge between A and B
using the parent of A as the common ancestor.

     A                          A'
    /                          /
   A^... pseudo history ...---B

When your history has renamed Makefile to Makefile2 (thereby losing
Makefile) while transition from A^ to A modified Makefile, the difference
between A^ to A that is applied to B to produce A' contains only the
change about Makefile (and does not talk about the unchangedness of
Makefile1 nor Makefile2 --- in fact, when A' is created, the machinery
does not even know if A^ and A had Makefile1 or Makefile2).

When applying the change to Makefile, it notices that B does not have
Makefile, but there is a path that is _identical_ to the preimage your
change applies to (namely, Makefile2).  To support people who rename
Makefile to Makefile2 in the history that led to B, rebase (actually the
underlying "am -3" it calls is where this rename detection smart lies)
applies the changes to the "renamed" path.

You might be able to work this around by forcing rebase not to use the
simplified 3-way merge, by saying "rebase -m".

Re: overly smart rebase - bug or feature?

[Avery Pennarun]

On Mon, Nov 10, 2008 at 6:14 PM, Junio C Hamano <gitster@pobox.com> wrote:
> When applying the change to Makefile, it notices that B does not have
> Makefile, but there is a path that is _identical_ to the preimage your
> change applies to (namely, Makefile2).  To support people who rename
> Makefile to Makefile2 in the history that led to B, rebase (actually the
> underlying "am -3" it calls is where this rename detection smart lies)
> applies the changes to the "renamed" path.

But isn't rename detection in this case rather suspicious, since:

- the preimage already had Makefile, Makefile1, and Makefile2, thus it
is not a rename, but at most a copy, and not even a newly-created copy
in either branch;

- *two* different files match the original Makefile, but rebase has
randomly selected one but not the other;

- (I haven't verified this claim) cherry-pick and merge both correctly
identify the problem as a delete/modify conflict?

It seems that rebase should have bailed out for at least one of these
three reasons.

Avery

Re: overly smart rebase - bug or feature?

[Fedor Sergeev]

On Mon, Nov 10, 2008 at 03:14:42PM -0800, Junio C Hamano wrote:
> Fedor Sergeev <Fedor.Sergeev@Sun.COM> writes:
> 
> > I have recently hit a behavior which might well be a feature, 
> > but it was very surprising (in a bad sense) to me.
> 
> It is a feature misfiring.
> 
> Rebase is essentially a repeated cherry-pick, and a cherry-pick of commit

But cherry-pick does fail, as shown in my original mail!

> A on top of commit B is done by a simplified 3-way merge between A and B
> using the parent of A as the common ancestor.
> 
>      A                          A'
>     /                          /
>    A^... pseudo history ...---B

Well, my history is exactly that, not pseudo (and I dont quite follow your reasoning
yet to understand whether this is important or not):

   A   B
    \ /
     A^

A^ *is* a common ancestor of both A and B.

> 
> When your history has renamed Makefile to Makefile2 (thereby losing
> Makefile)

My history did not rename Makefile.
There were three identical Makefiles (in A^)
After that one was deleted (in B).
On alternative branch it was edited (in A).

If I do *merge* A into B then it fails.
If I do *cherry-pick* A into B then it fails.
If I do *rebase* A onto B then it succeeds.

> while transition from A^ to A modified Makefile, the difference
> between A^ to A that is applied to B to produce A' contains only the
> change about Makefile (and does not talk about the unchangedness of
> Makefile1 nor Makefile2 --- in fact, when A' is created, the machinery
> does not even know if A^ and A had Makefile1 or Makefile2).
> 
> When applying the change to Makefile, it notices that B does not have
> Makefile, but there is a path that is _identical_ to the preimage your
> change applies to (namely, Makefile2).  To support people who rename
> Makefile to Makefile2 in the history that led to B

There was no rename. There was a copy in initial commit (and you cant say if it
was Makefile copied into Makefile2 or vice verse).
I dont believe it should really be called "rename", even if one of the copies was killed later.

>, rebase (actually the
> underlying "am -3" it calls is where this rename detection smart lies)
> applies the changes to the "renamed" path.

In this given case both Makefile1 and Makefile2 were absolutely equal. 
If rebase chose to edit Makefile2 why didnt it change Makefile1?

> 
> You might be able to work this around by forcing rebase not to use the
> simplified 3-way merge, by saying "rebase -m".

Yeah, it worked.
...
CONFLICT (delete/modify): Makefile deleted in master and modified in HEAD~0. Version HEAD~0 of Makefile left in tree.
...

Though it does make me wonder why *simplified* 3-way merge is smarter than git merge ;)))

best regards,
  Fedor..

Re: overly smart rebase - bug or feature?

[Junio C Hamano]

Fedor Sergeev <Fedor.Sergeev@Sun.COM> writes:

> On Mon, Nov 10, 2008 at 03:14:42PM -0800, Junio C Hamano wrote:
>> Fedor Sergeev <Fedor.Sergeev@Sun.COM> writes:
>> 
>> > I have recently hit a behavior which might well be a feature, 
>> > but it was very surprising (in a bad sense) to me.
>> 
>> It is a feature misfiring.
>> 
>> Rebase is essentially a repeated cherry-pick, and a cherry-pick of commit
>
> But cherry-pick does fail, as shown in my original mail!
>
>> A on top of commit B is done by a simplified 3-way merge between A and B
>> using the parent of A as the common ancestor.
>> 
>>      A                          A'
>>     /                          /
>>    A^... pseudo history ...---B
>
> Well, my history is exactly that, not pseudo (and I dont quite follow your reasoning
> yet to understand whether this is important or not):
>
>    A   B
>     \ /
>      A^
>
> A^ *is* a common ancestor of both A and B.
>
>> 
>> When your history has renamed Makefile to Makefile2 (thereby losing
>> Makefile)
>
> My history did not rename Makefile.
> There were three identical Makefiles (in A^)
> After that one was deleted (in B).
> On alternative branch it was edited (in A).
>
> If I do *merge* A into B then it fails.
> If I do *cherry-pick* A into B then it fails.
> If I do *rebase* A onto B then it succeeds.
>
>> while transition from A^ to A modified Makefile, the difference
>> between A^ to A that is applied to B to produce A' contains only the
>> change about Makefile (and does not talk about the unchangedness of
>> Makefile1 nor Makefile2 --- in fact, when A' is created, the machinery
>> does not even know if A^ and A had Makefile1 or Makefile2).
>> 
>> When applying the change to Makefile, it notices that B does not have
>> Makefile, but there is a path that is _identical_ to the preimage your
>> change applies to (namely, Makefile2).  To support people who rename
>> Makefile to Makefile2 in the history that led to B
>
> There was no rename. There was a copy in initial commit (and you cant say if it
> was Makefile copied into Makefile2 or vice verse).
> I dont believe it should really be called "rename", even if one of the copies was killed later.
>
>>, rebase (actually the
>> underlying "am -3" it calls is where this rename detection smart lies)
>> applies the changes to the "renamed" path.
>
> In this given case both Makefile1 and Makefile2 were absolutely equal. 
> If rebase chose to edit Makefile2 why didnt it change Makefile1?
>
>> 
>> You might be able to work this around by forcing rebase not to use the
>> simplified 3-way merge, by saying "rebase -m".
>
> Yeah, it worked.
> ...
> CONFLICT (delete/modify): Makefile deleted in master and modified in HEAD~0. Version HEAD~0 of Makefile left in tree.
> ...
>
> Though it does make me wonder why *simplified* 3-way merge is smarter than git merge ;)))

Simplified one is not _smarter_.  It is merely _faster_, exactly because
it only looks at the paths between A^..A and nothing else.

And that is why it cannot tell between the case where both A^ and A have
Makefile2 or they both lack it.  And that is exactly why application of
this change on top of B is mistaken as a patch to a renamed path.  From
B's point of view:

 - Incoming change says "I changed Makefile from this shape to that
   shape", and nothing else;

 - B does not have Makefile, but it happens to have the contents at path
   Makefile2 that is identical to the preimage of that incoming change.

which makes it guess (when falling back to 3-way merge) that somewhere
leading to B what used to be at Makefile (which is what the incoming
change claims to change) may have been renamed to Makefile2 (because B
does not have Makefile but does have it).

Re: overly smart rebase - bug or feature?

[Fedor Sergeev]

On Mon, Nov 10, 2008, Junio C Hamano wrote:
> Fedor Sergeev <Fedor.Sergeev@Sun.COM> writes:
> >> You might be able to work this around by forcing rebase not to use the
> >> simplified 3-way merge, by saying "rebase -m".
> >
> > Yeah, it worked.
> > ...
> > CONFLICT (delete/modify): Makefile deleted in master and modified in HEAD~0. Version HEAD~0 of Makefile left in tree.
> > ...
> >
> > Though it does make me wonder why *simplified* 3-way merge is smarter than git merge ;)))
> 
> Simplified one is not _smarter_.  It is merely _faster_, exactly because
> it only looks at the paths between A^..A and nothing else.

I seem to start getting grasp on it.
Please, correct me if I'm wrong:
  - by default rebase uses "simplified" merge, which (roughly speaking) 
    simply goes around patching parent with changes from either branches A and B

  - rebase -m applies 'recursive' merge (default merge strategy) which is 
    kind of smarter and determines a conflict in my case

  - literally the same happens when I do merge instead of rebase 

  - cherry-pick fails just because "patch B" can not apply to A and that is
    literally why rebase started falling out to *some* merge first hand

If the above is true then can you, please, answer the following questions:
  - is there any merge strategy that can do "simplified" merge just like that in rebase?
    (not that I need it, but just for educational purpose)

  - does rebase perform simplified merge only because of speed considerations?
    (e.g. are there any correctness/usability issues with using smarter merge algo on rebase) 

  - is there any .git/config variable that affects which merge to use upon rebase?

best regards,
  Fedor.

Re: overly smart rebase - bug or feature?

[Junio C Hamano]

Fedor Sergeev <Fedor.Sergeev@Sun.COM> writes:

> Please, correct me if I'm wrong:
>
>   - by default rebase uses "simplified" merge, which (roughly speaking) 
>     simply goes around patching parent with changes from either branches A and B
>
>   - rebase -m applies 'recursive' merge (default merge strategy) which is 
>     kind of smarter and determines a conflict in my case
>
>   - literally the same happens when I do merge instead of rebase 

If "the same" means "always use 'recursive' merge, without 'am -3'
(mis)behaviour seen in rebase", then yes.

>   - cherry-pick fails just because "patch B" can not apply to A and that is
>     literally why rebase started falling out to *some* merge first hand

I do not know about this part.  Rebase _conceptually_ does cherry-pick but
uses a different implementation.

> If the above is true then can you, please, answer the following questions:

I'll answer the one that cannot be answered without knowing history.  I
suspect answers to your other questions are found in the doc set.

>   - does rebase perform simplified merge only because of speed considerations?

Historical accident.  Originally rebase was only "format-patch | am",
i.e. lift a patch from the commits to be rebased, apply them in order.

Later, "am -3" was invented that allows you to apply patches with fuzz by
using 3-way merge at the content level, which was successfull and rebase
was taught about using it.