Apparent bug in git rebase with a merge commit

Apparent bug in git rebase with a merge commit

[David M. Lloyd]

If you have a git tree and you merge in another, independent git tree so 
that they are the same, using a merge strategy like this:

$ git merge importing/master -s recursive -Xours

And if you later on want to rebase this merge commit on a newer upstream 
for whatever reason, you get something like this:

$ git rebase -s recursive -Xours
First, rewinding head to replay your work on top of it...
fatal: Could not parse object 'ca59931ee67fc01b4db4278600d3d92aece898f4^'
Unknown exit code (128) from command: git-merge-recursive 
ca59931ee67fc01b4db4278600d3d92aece898f4^ -- HEAD 
ca59931ee67fc01b4db4278600d3d92aece898f4

The reason this occurs is that the first commit of the newly-merged-in 
code obviously has no parent, so I guess the search for the common 
ancestor is going to be doomed to fail.

It is possible that I'm misunderstanding the recursive merge strategy; 
however if this were the case I'd still expect a human-readable error 
message explaining my mistake rather than a 128 exit code.

For a workaround I'll just re-create the commit, but I thought I'd 
report this behavior anyway.
-- 
- DML

[PATCH v1] rebase -m: Use empty tree base for parentless commits

[Fabian Ruch]

When the user specifies a merge strategy, `git-merge-$strategy` is
used in non-interactive mode to replay the changes introduced by the
current branch relative to some upstream. Specifically, for each
commit `c` that is not in upstream the changes that led from `c^` to
`c` are reapplied.

If the current has a different root than the upstream, either because
the history is disconnected or merged in a disconnected history, then
there will be a parentless commit `c` and `c^` will not refer to a
commit.

In order to cope with such a situation, check for every `c` whether
its list of parents is empty. If it is empty, determine the
introduced changes by comparing the committed tree to the empty tree
instead. Otherwise, take the differences between `c^` and `c` as
before.

The other git-rebase modes do not have similar problems because they
use git-cherry-pick to replay changes, even with strategy options. It
seems that the non-interactive rebase with merge strategies was not
implemented using git-cherry-pick because it did not support them at
the time (`git rebase --merge` added in 58634dbf and `git cherry-pick
--strategy` added in 91e52598). The idea of using the empty tree as
reference tree for orphan commits is taken from the git-cherry-pick
implementation.

Regarding the patch, we do not have to commit the empty tree before
we can pass it as a base argument to `git-merge-$strategy` because
tree objects are recognized as such and implicitly committed by
`git-merge-$strategy`.

Add a test. The test case rebases a single disconnected commit which
creates an isolated file on master and, therefore, does not require a
specific merge strategy. It is a mere sanity check.

Reported-by: David M. Lloyd <david.lloyd@redhat.com>
Signed-off-by: Fabian Ruch <bafain@gmail.com>
---
Hi David,

I don't think you made a mistake at all. If I understand the --merge
mode of git-rebase correctly there is no need to require a parent.
The error occurs when the script tries to determine the changes your
merge commit introduces, which includes the whole "importing/master"
branch. The strategy is not yet part of the picture then and will not
be until the changes are being replayed.

The test case tries to simplify your scenario because the relevant
characteristic seems to be that a parentless commit gets rebased, the
root commit of "importing/master".

Regards,
   Fabian

 git-rebase--merge.sh          |  8 +++++++-
 t/t3400-rebase.sh             | 12 ++++++++++++
 t/t3402-rebase-merge.sh       | 12 ++++++++++++
 t/t3404-rebase-interactive.sh | 10 ++++++++++
 4 files changed, 41 insertions(+), 1 deletion(-)

diff --git a/git-rebase--merge.sh b/git-rebase--merge.sh
index d3fb67d..3f754ae 100644
--- a/git-rebase--merge.sh
+++ b/git-rebase--merge.sh
@@ -67,7 +67,13 @@ call_merge () {
 		GIT_MERGE_VERBOSITY=1 && export GIT_MERGE_VERBOSITY
 	fi
 	test -z "$strategy" && strategy=recursive
-	eval 'git-merge-$strategy' $strategy_opts '"$cmt^" -- "$hd" "$cmt"'
+	base=$(git rev-list --parents -1 $cmt | cut -d ' ' -s -f 2 -)
+	if test -z "$base"
+	then
+		# the empty tree sha1
+		base=4b825dc642cb6eb9a060e54bf8d69288fbee4904
+	fi
+	eval 'git-merge-$strategy' $strategy_opts '"$base" -- "$hd" "$cmt"'
 	rv=$?
 	case "$rv" in
 	0)
diff --git a/t/t3400-rebase.sh b/t/t3400-rebase.sh
index 47b5682..9b0b57f 100755
--- a/t/t3400-rebase.sh
+++ b/t/t3400-rebase.sh
@@ -10,6 +10,8 @@ among other things.
 '
 . ./test-lib.sh
 
+. "$TEST_DIRECTORY"/lib-rebase.sh
+
 GIT_AUTHOR_NAME=author@name
 GIT_AUTHOR_EMAIL=bogus@email@address
 export GIT_AUTHOR_NAME GIT_AUTHOR_EMAIL
@@ -255,4 +257,14 @@ test_expect_success 'rebase commit with an ancient timestamp' '
 	grep "author .* 34567 +0600$" actual
 '
 
+test_expect_success 'rebase disconnected' '
+	test_when_finished reset_rebase &&
+	git checkout --orphan test-rebase-disconnected &&
+	git rm -rf . &&
+	test_commit disconnected &&
+	git rebase master &&
+	test_path_is_file disconnected.t &&
+	test_cmp_rev master HEAD^
+'
+
 test_done
diff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh
index 5a27ec9..1653540 100755
--- a/t/t3402-rebase-merge.sh
+++ b/t/t3402-rebase-merge.sh
@@ -7,6 +7,8 @@ test_description='git rebase --merge test'
 
 . ./test-lib.sh
 
+. "$TEST_DIRECTORY"/lib-rebase.sh
+
 T="A quick brown fox
 jumps over the lazy dog."
 for i in 1 2 3 4 5 6 7 8 9 10
@@ -153,4 +155,14 @@ test_expect_success 'rebase --skip works with two conflicts in a row' '
 	git rebase --skip
 '
 
+test_expect_success 'rebase --merge disconnected' '
+	test_when_finished reset_rebase &&
+	git checkout --orphan test-rebase-disconnected &&
+	git rm -rf . &&
+	test_commit disconnected &&
+	git rebase --merge master &&
+	test_path_is_file disconnected.t &&
+	test_cmp_rev master HEAD^
+'
+
 test_done
diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index 8197ed2..858c036 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -1039,4 +1039,14 @@ test_expect_success 'short SHA-1 collide' '
 	)
 '
 
+test_expect_success 'rebase --interactive disconnected' '
+	test_when_finished reset_rebase &&
+	git checkout --orphan test-rebase-disconnected &&
+	git rm -rf . &&
+	test_commit disconnected &&
+	EDITOR=true git rebase --interactive master &&
+	test_path_is_file disconnected.t &&
+	test_cmp_rev master HEAD^
+'
+
 test_done
-- 
2.1.1

Re: [PATCH v1] rebase -m: Use empty tree base for parentless commits

[Junio C Hamano]

Fabian Ruch <bafain@gmail.com> writes:

> diff --git a/git-rebase--merge.sh b/git-rebase--merge.sh
> index d3fb67d..3f754ae 100644
> --- a/git-rebase--merge.sh
> +++ b/git-rebase--merge.sh
> @@ -67,7 +67,13 @@ call_merge () {
>  		GIT_MERGE_VERBOSITY=1 && export GIT_MERGE_VERBOSITY
>  	fi
>  	test -z "$strategy" && strategy=recursive
> -	eval 'git-merge-$strategy' $strategy_opts '"$cmt^" -- "$hd" "$cmt"'
> +	base=$(git rev-list --parents -1 $cmt | cut -d ' ' -s -f 2 -)
> +	if test -z "$base"
> +	then
> +		# the empty tree sha1
> +		base=4b825dc642cb6eb9a060e54bf8d69288fbee4904
> +	fi
> +	eval 'git-merge-$strategy' $strategy_opts '"$base" -- "$hd" "$cmt"'

This looks wrong.

The interface to "git-merge-$strategy" is designed in such a way
that each strategy should be capable of taking _no_ base at all.

See how unquoted $common is given to git-merge-$strategy in
contrib/examples/git-merge.sh, i.e.

    eval 'git-merge-$strategy '"$xopt"' $common -- "$head_arg" "$@"'

where common comes from

	common=$(git merge-base ...)

which would be empty when you are looking at disjoint histories.

Also rev-list piped to cut is too ugly to live in our codebase X-<.

Wouldn't it be sufficient to do something like this instead?

	eval 'git-merge-$strategy' $strategy_opts \
        	$(git rev-parse --quiet --verify "$cmt^") -- "$hd" "$cmt"

Re: [PATCH v1] rebase -m: Use empty tree base for parentless commits

[Derek Moore]

Should perhaps you be using some symbolic method of referencing the
empty tree instead of referencing a magic number?

E.g., https://git.wiki.kernel.org/index.php/Aliases#Obtaining_the_Empty_Tree_SHA1

On Thu, Oct 9, 2014 at 1:50 PM, Fabian Ruch <bafain@gmail.com> wrote:
> When the user specifies a merge strategy, `git-merge-$strategy` is
> used in non-interactive mode to replay the changes introduced by the
> current branch relative to some upstream. Specifically, for each
> commit `c` that is not in upstream the changes that led from `c^` to
> `c` are reapplied.
>
> If the current has a different root than the upstream, either because
> the history is disconnected or merged in a disconnected history, then
> there will be a parentless commit `c` and `c^` will not refer to a
> commit.
>
> In order to cope with such a situation, check for every `c` whether
> its list of parents is empty. If it is empty, determine the
> introduced changes by comparing the committed tree to the empty tree
> instead. Otherwise, take the differences between `c^` and `c` as
> before.
>
> The other git-rebase modes do not have similar problems because they
> use git-cherry-pick to replay changes, even with strategy options. It
> seems that the non-interactive rebase with merge strategies was not
> implemented using git-cherry-pick because it did not support them at
> the time (`git rebase --merge` added in 58634dbf and `git cherry-pick
> --strategy` added in 91e52598). The idea of using the empty tree as
> reference tree for orphan commits is taken from the git-cherry-pick
> implementation.
>
> Regarding the patch, we do not have to commit the empty tree before
> we can pass it as a base argument to `git-merge-$strategy` because
> tree objects are recognized as such and implicitly committed by
> `git-merge-$strategy`.
>
> Add a test. The test case rebases a single disconnected commit which
> creates an isolated file on master and, therefore, does not require a
> specific merge strategy. It is a mere sanity check.
>
> Reported-by: David M. Lloyd <david.lloyd@redhat.com>
> Signed-off-by: Fabian Ruch <bafain@gmail.com>
> ---
> Hi David,
>
> I don't think you made a mistake at all. If I understand the --merge
> mode of git-rebase correctly there is no need to require a parent.
> The error occurs when the script tries to determine the changes your
> merge commit introduces, which includes the whole "importing/master"
> branch. The strategy is not yet part of the picture then and will not
> be until the changes are being replayed.
>
> The test case tries to simplify your scenario because the relevant
> characteristic seems to be that a parentless commit gets rebased, the
> root commit of "importing/master".
>
> Regards,
>    Fabian
>
>  git-rebase--merge.sh          |  8 +++++++-
>  t/t3400-rebase.sh             | 12 ++++++++++++
>  t/t3402-rebase-merge.sh       | 12 ++++++++++++
>  t/t3404-rebase-interactive.sh | 10 ++++++++++
>  4 files changed, 41 insertions(+), 1 deletion(-)
>
> diff --git a/git-rebase--merge.sh b/git-rebase--merge.sh
> index d3fb67d..3f754ae 100644
> --- a/git-rebase--merge.sh
> +++ b/git-rebase--merge.sh
> @@ -67,7 +67,13 @@ call_merge () {
>                 GIT_MERGE_VERBOSITY=1 && export GIT_MERGE_VERBOSITY
>         fi
>         test -z "$strategy" && strategy=recursive
> -       eval 'git-merge-$strategy' $strategy_opts '"$cmt^" -- "$hd" "$cmt"'
> +       base=$(git rev-list --parents -1 $cmt | cut -d ' ' -s -f 2 -)
> +       if test -z "$base"
> +       then
> +               # the empty tree sha1
> +               base=4b825dc642cb6eb9a060e54bf8d69288fbee4904
> +       fi
> +       eval 'git-merge-$strategy' $strategy_opts '"$base" -- "$hd" "$cmt"'
>         rv=$?
>         case "$rv" in
>         0)
> diff --git a/t/t3400-rebase.sh b/t/t3400-rebase.sh
> index 47b5682..9b0b57f 100755
> --- a/t/t3400-rebase.sh
> +++ b/t/t3400-rebase.sh
> @@ -10,6 +10,8 @@ among other things.
>  '
>  . ./test-lib.sh
>
> +. "$TEST_DIRECTORY"/lib-rebase.sh
> +
>  GIT_AUTHOR_NAME=author@name
>  GIT_AUTHOR_EMAIL=bogus@email@address
>  export GIT_AUTHOR_NAME GIT_AUTHOR_EMAIL
> @@ -255,4 +257,14 @@ test_expect_success 'rebase commit with an ancient timestamp' '
>         grep "author .* 34567 +0600$" actual
>  '
>
> +test_expect_success 'rebase disconnected' '
> +       test_when_finished reset_rebase &&
> +       git checkout --orphan test-rebase-disconnected &&
> +       git rm -rf . &&
> +       test_commit disconnected &&
> +       git rebase master &&
> +       test_path_is_file disconnected.t &&
> +       test_cmp_rev master HEAD^
> +'
> +
>  test_done
> diff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh
> index 5a27ec9..1653540 100755
> --- a/t/t3402-rebase-merge.sh
> +++ b/t/t3402-rebase-merge.sh
> @@ -7,6 +7,8 @@ test_description='git rebase --merge test'
>
>  . ./test-lib.sh
>
> +. "$TEST_DIRECTORY"/lib-rebase.sh
> +
>  T="A quick brown fox
>  jumps over the lazy dog."
>  for i in 1 2 3 4 5 6 7 8 9 10
> @@ -153,4 +155,14 @@ test_expect_success 'rebase --skip works with two conflicts in a row' '
>         git rebase --skip
>  '
>
> +test_expect_success 'rebase --merge disconnected' '
> +       test_when_finished reset_rebase &&
> +       git checkout --orphan test-rebase-disconnected &&
> +       git rm -rf . &&
> +       test_commit disconnected &&
> +       git rebase --merge master &&
> +       test_path_is_file disconnected.t &&
> +       test_cmp_rev master HEAD^
> +'
> +
>  test_done
> diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
> index 8197ed2..858c036 100755
> --- a/t/t3404-rebase-interactive.sh
> +++ b/t/t3404-rebase-interactive.sh
> @@ -1039,4 +1039,14 @@ test_expect_success 'short SHA-1 collide' '
>         )
>  '
>
> +test_expect_success 'rebase --interactive disconnected' '
> +       test_when_finished reset_rebase &&
> +       git checkout --orphan test-rebase-disconnected &&
> +       git rm -rf . &&
> +       test_commit disconnected &&
> +       EDITOR=true git rebase --interactive master &&
> +       test_path_is_file disconnected.t &&
> +       test_cmp_rev master HEAD^
> +'
> +
>  test_done
> --
> 2.1.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v1] rebase -m: Use empty tree base for parentless commits

[David M. Lloyd]

On 10/09/2014 01:50 PM, Fabian Ruch wrote:
> Hi David,
>
> I don't think you made a mistake at all. If I understand the --merge
> mode of git-rebase correctly there is no need to require a parent.
> The error occurs when the script tries to determine the changes your
> merge commit introduces, which includes the whole "importing/master"
> branch. The strategy is not yet part of the picture then and will not
> be until the changes are being replayed.

Thank you for your prompt response, clear explanation, and patch even! 
I'm afraid my understanding of the git internals is next-to-nil.  But 
I'm glad I could contribute to helping to improve it in some small way.

-- 
- DML

Re: [PATCH v1] rebase -m: Use empty tree base for parentless commits

[Fabian Ruch]

Hi Junio,

On 10/09/2014 09:05 PM, Junio C Hamano wrote:
> Fabian Ruch <bafain@gmail.com> writes:
>> diff --git a/git-rebase--merge.sh b/git-rebase--merge.sh
>> index d3fb67d..3f754ae 100644
>> --- a/git-rebase--merge.sh
>> +++ b/git-rebase--merge.sh
>> @@ -67,7 +67,13 @@ call_merge () {
>>  		GIT_MERGE_VERBOSITY=1 && export GIT_MERGE_VERBOSITY
>>  	fi
>>  	test -z "$strategy" && strategy=recursive
>> -	eval 'git-merge-$strategy' $strategy_opts '"$cmt^" -- "$hd" "$cmt"'
>> +	base=$(git rev-list --parents -1 $cmt | cut -d ' ' -s -f 2 -)
>> +	if test -z "$base"
>> +	then
>> +		# the empty tree sha1
>> +		base=4b825dc642cb6eb9a060e54bf8d69288fbee4904
>> +	fi
>> +	eval 'git-merge-$strategy' $strategy_opts '"$base" -- "$hd" "$cmt"'
> 
> This looks wrong.

Ok.

> The interface to "git-merge-$strategy" is designed in such a way
> that each strategy should be capable of taking _no_ base at all.

The merge strategies "resolve" and "octopus" seem to refuse to run if no
base is specified. The former silently exits if no bases are given and
the latter dies saying "Unable to find common commit".

> See how unquoted $common is given to git-merge-$strategy in
> contrib/examples/git-merge.sh, i.e.
> 
>     eval 'git-merge-$strategy '"$xopt"' $common -- "$head_arg" "$@"'
> 
> where common comes from
> 
> 	common=$(git merge-base ...)
> 
> which would be empty when you are looking at disjoint histories.
> 
> Also rev-list piped to cut is too ugly to live in our codebase X-<.

Is there a better way to get the parents list from a shell script then?
I stole the construct from git-rebase--interactive.sh which uses it to
check for rewritten parents when preserving merges.

> Wouldn't it be sufficient to do something like this instead?
> 
> 	eval 'git-merge-$strategy' $strategy_opts \
>         	$(git rev-parse --quiet --verify "$cmt^") -- "$hd" "$cmt"

Yes, for the "recursive" strategies this seems to have the exact same
behaviour as it inserts the empty tree in case git-merge-base returns an
empty list. Nice, we would get rid of both the magic number and the cut.

Regards,
   Fabian

Re: [PATCH v1] rebase -m: Use empty tree base for parentless commits

[Junio C Hamano]

Fabian Ruch <bafain@gmail.com> writes:

>> The interface to "git-merge-$strategy" is designed in such a way
>> that each strategy should be capable of taking _no_ base at all.
>
> The merge strategies "resolve" and "octopus" seem to refuse to run if no
> base is specified. The former silently exits if no bases are given and
> the latter dies saying "Unable to find common commit".

That just means these two strategies are not prepared to do a merge
without base (yet).  It does not automatically give license to the
caller to pass a random tree as if it is the merge base the user
wanted to use.

For "resolve", I think it is OK for it to detect that the caller did
not give a common ancestor tree and use an empty tree when merging
(which is what merge-recursive ends up doing internally).

I am not offhand sure if the same is sensible for "octopus", though.

Re: [PATCH v1] rebase -m: Use empty tree base for parentless commits

[Fabian Ruch]

Hi,

Junio C Hamano writes:
> Fabian Ruch <bafain@gmail.com> writes:
>> diff --git a/git-rebase--merge.sh b/git-rebase--merge.sh
>> index d3fb67d..3f754ae 100644
>> --- a/git-rebase--merge.sh
>> +++ b/git-rebase--merge.sh
>> @@ -67,7 +67,13 @@ call_merge () {
>>  		GIT_MERGE_VERBOSITY=1 && export GIT_MERGE_VERBOSITY
>>  	fi
>>  	test -z "$strategy" && strategy=recursive
>> -	eval 'git-merge-$strategy' $strategy_opts '"$cmt^" -- "$hd" "$cmt"'
>> +	base=$(git rev-list --parents -1 $cmt | cut -d ' ' -s -f 2 -)
>> +	if test -z "$base"
>> +	then
>> +		# the empty tree sha1
>> +		base=4b825dc642cb6eb9a060e54bf8d69288fbee4904
>> +	fi
>> +	eval 'git-merge-$strategy' $strategy_opts '"$base" -- "$hd" "$cmt"'
> 
> This looks wrong.
> 
> The interface to "git-merge-$strategy" is designed in such a way
> that each strategy should be capable of taking _no_ base at all.

Ok, but doesn't this use of the git-merge-$strategy interface (as shown
in the example below) apply only to the case where one wants to merge
two histories by creating a merge commit? When a merge commit is being
created, the documentation states that git-merge abstracts from the
commit history considering the _total change_ since a merge base on each
branch.

In contrast, here (i.e., in the case of git-rebase--merge) we care about
how the changes introduced by the _individual commits_ are applied.
Therefore, don't we want to be explicit about the "base" and tell
git-merge-$strategy exactly which changes it should merge into the
current head?

The codebase has always been doing this both for git-rebase--merge and
git-cherry-pick. What leads to the reported bug is that the latter
covers the case where the commit object has no parents but the former
doesn't. Root commits are handled by git-cherry-pick (and should be by
git-rebase--merge) using an explicit "base" for the same reason why
$cmt^ is given.

> See how unquoted $common is given to git-merge-$strategy in
> contrib/examples/git-merge.sh, i.e.
> 
>     eval 'git-merge-$strategy '"$xopt"' $common -- "$head_arg" "$@"'
> 
> where common comes from
> 
> 	common=$(git merge-base ...)
> 
> which would be empty when you are looking at disjoint histories.

If there are still objections to the patch because of the magic number
and the cut, it might be worth considering an implementation of
git-rebase--merge using git-cherry-pick's merge strategy option.

   Fabian