[PATCH 0/3] fix interactive rebase short SHA-1 collision bug

[PATCH 0/3] fix interactive rebase short SHA-1 collision bug

[Eric Sunshine]

This series addresses a bug [1][2] which can manifest during interactive
rebase when the prefix of the new SHA-1 of an edited commit is shared
with the abbreviated SHA-1 of a subsequent commit in the 'todo' list.
When rebase attempts to process the subsequent command, it dies with a
"short SHA1 badbeef is ambiguous" error.

patch 1: fix a problem in the interactive rebase test suite which can
    make subsequent tests fail

patch 2: add a test demonstrating the short SHA-1 collision bug

patch 3: fix the bug (this patch is from Junio [3] but augmented also to
    fix up "rebase --edit-todo")

[1]: http://thread.gmane.org/gmane.comp.version-control.git/229091
[2]: http://thread.gmane.org/gmane.comp.version-control.git/232012
[3]: http://thread.gmane.org/gmane.comp.version-control.git/229091/focus=229120

Eric Sunshine (2):
  t3404: restore specialized rebase-editor following commentchar test
  t3404: rebase: interactive: demonstrate short SHA-1 collision

Junio C Hamano (1):
  rebase: interactive: fix short SHA-1 collision

 git-rebase--interactive.sh    | 30 ++++++++++++++++++++++++++++++
 t/t3404-rebase-interactive.sh | 18 ++++++++++++++++++
 2 files changed, 48 insertions(+)

-- 
1.8.4.rc2.460.ga591f4a

[PATCH 1/3] t3404: restore specialized rebase-editor following commentchar test

[Eric Sunshine]

At start of script, t3404 installs a specialized test-editor ($EDITOR)
upon which many of the interactive rebase tests depend.  Late in t3404,
test "rebase -i respects core.commentchar" installs its own custom
editor but neglects to restore the specialized editor when finished.
This oversight will cause later tests, which require the specialized
editor, to fail.  (There are no such tests presently, but a subsequent
patch will introduce one.)  Fix this problem.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
---
 t/t3404-rebase-interactive.sh | 1 +
 1 file changed, 1 insertion(+)

diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index 49ccb38..af141be 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -949,6 +949,7 @@ test_expect_success 'rebase -i respects core.commentchar' '
 	sed -e "2,\$s/^/\\\\/" "$1" >"$1.tmp" &&
 	mv "$1.tmp" "$1"
 	EOF
+	test_when_finished "set_fake_editor" &&
 	test_set_editor "$(pwd)/remove-all-but-first.sh" &&
 	git rebase -i B &&
 	test B = $(git cat-file commit HEAD^ | sed -ne \$p)
-- 
1.8.4.rc2.460.ga591f4a

[PATCH 2/3] t3404: rebase: interactive: demonstrate short SHA-1 collision

[Eric Sunshine]

The 'todo' sheet for interactive rebase shows abbreviated SHA-1's and
then performs its operations upon those shortened values. This can lead
to an abort if the SHA-1 of a reworded or edited commit is no longer
unique within the abbreviated SHA-1 space and a subsequent SHA-1 in the
todo list has the same abbreviated value.

For example:

  edit f00dfad first
  pick badbeef second

If, after editing, the new SHA-1 of "first" is now
badbeef5ba78983324dff5265c80c4490d5a809a, then the subsequent 'pick
badbeef second' will fail since badbeef is no longer a unique SHA-1
abbreviation:

  error: short SHA1 badbeef is ambiguous.
  fatal: Needed a single revision
  Invalid commit name: badbeef

Demonstrate this problem with a couple of specially crafted commits
which initially have distinct abbreviated SHA-1's, but for which the
abbreviated SHA-1's collide after a simple rewording of the first
commit's message.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
---
 t/t3404-rebase-interactive.sh | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index af141be..e5ebec6 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -977,4 +977,21 @@ test_expect_success 'rebase -i with --strategy and -X' '
 	test $(cat file1) = Z
 '
 
+test_expect_success 'short SHA-1 setup' '
+	test_when_finished "git checkout master" &&
+	git checkout --orphan collide &&
+	git rm -rf . &&
+	unset test_tick &&
+	test_commit collide1 collide &&
+	test_commit --notick collide2 collide &&
+	test_commit --notick "collide3 115158b5" collide collide3 collide3
+'
+
+test_expect_failure 'short SHA-1 collide' '
+	test_when_finished "reset_rebase && git checkout master" &&
+	git checkout collide &&
+	FAKE_COMMIT_MESSAGE="collide2 815200e" \
+	FAKE_LINES="reword 1 2" git rebase -i HEAD~2
+'
+
 test_done
-- 
1.8.4.rc2.460.ga591f4a

[PATCH 3/3] rebase: interactive: fix short SHA-1 collision

[Eric Sunshine]

From: Junio C Hamano <gitster@pobox.com>

The 'todo' sheet for interactive rebase shows abbreviated SHA-1's and
then performs its operations upon those shortened values. This can lead
to an abort if the SHA-1 of a reworded or edited commit is no longer
unique within the abbreviated SHA-1 space and a subsequent SHA-1 in the
todo list has the same abbreviated value.

For example:

  edit f00dfad first
  pick badbeef second

If, after editing, the new SHA-1 of "first" is now
badbeef5ba78983324dff5265c80c4490d5a809a, then the subsequent 'pick
badbeef second' will fail since badbeef is no longer a unique SHA-1
abbreviation:

  error: short SHA1 badbeef is ambiguous.
  fatal: Needed a single revision
  Invalid commit name: badbeef

Fix this problem by expanding the SHA-1's in the todo list before
performing the operations.

[es: also collapse & expand SHA-1's for --edit-todo]

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
---
 git-rebase--interactive.sh    | 30 ++++++++++++++++++++++++++++++
 t/t3404-rebase-interactive.sh |  2 +-
 2 files changed, 31 insertions(+), 1 deletion(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 83d6d46..ea11e62 100644
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -689,6 +689,32 @@ skip_unnecessary_picks () {
 	die "Could not skip unnecessary pick commands"
 }
 
+transform_todo_ids () {
+	while read -r command rest
+	do
+		case "$command" in
+		'#'* | exec)
+			# Be careful for oddball commands like 'exec'
+			# that do not have a SHA-1 at the beginning of $rest.
+			;;
+		*)
+			sha1=$(git rev-parse --verify --quiet "$@" ${rest%% *}) &&
+			rest="$sha1 ${rest#* }"
+			;;
+		esac
+		printf '%s\n' "$command${rest:+ }$rest"
+	done <"$todo" >"$todo.new" &&
+	mv -f "$todo.new" "$todo"
+}
+
+expand_todo_ids() {
+	transform_todo_ids
+}
+
+collapse_todo_ids() {
+	transform_todo_ids --short=7
+}
+
 # Rearrange the todo list that has both "pick sha1 msg" and
 # "pick sha1 fixup!/squash! msg" appears in it so that the latter
 # comes immediately after the former, and change "pick" to
@@ -841,6 +867,7 @@ skip)
 edit-todo)
 	git stripspace --strip-comments <"$todo" >"$todo".new
 	mv -f "$todo".new "$todo"
+	collapse_todo_ids
 	append_todo_help
 	git stripspace --comment-lines >>"$todo" <<\EOF
 
@@ -852,6 +879,7 @@ EOF
 
 	git_sequence_editor "$todo" ||
 		die "Could not execute editor"
+	expand_todo_ids
 
 	exit
 	;;
@@ -1008,6 +1036,8 @@ git_sequence_editor "$todo" ||
 has_action "$todo" ||
 	die_abort "Nothing to do"
 
+expand_todo_ids
+
 test -d "$rewritten" || test -n "$force_rebase" || skip_unnecessary_picks
 
 GIT_REFLOG_ACTION="$GIT_REFLOG_ACTION: checkout $onto_name"
diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
index e5ebec6..db56db3 100755
--- a/t/t3404-rebase-interactive.sh
+++ b/t/t3404-rebase-interactive.sh
@@ -987,7 +987,7 @@ test_expect_success 'short SHA-1 setup' '
 	test_commit --notick "collide3 115158b5" collide collide3 collide3
 '
 
-test_expect_failure 'short SHA-1 collide' '
+test_expect_success 'short SHA-1 collide' '
 	test_when_finished "reset_rebase && git checkout master" &&
 	git checkout collide &&
 	FAKE_COMMIT_MESSAGE="collide2 815200e" \
-- 
1.8.4.rc2.460.ga591f4a

Re: [PATCH 1/3] t3404: restore specialized rebase-editor following commentchar test

[Junio C Hamano]

Eric Sunshine <sunshine@sunshineco.com> writes:

> At start of script, t3404 installs a specialized test-editor ($EDITOR)
> upon which many of the interactive rebase tests depend.  Late in t3404,
> test "rebase -i respects core.commentchar" installs its own custom
> editor but neglects to restore the specialized editor when finished.
> This oversight will cause later tests, which require the specialized
> editor, to fail. 

That is not oversight but was deliberately done knowing that it will
be the last test (and new tests can be added before it).

I think the patch is one way to give _known_ status to later tests
by declaring the editor installed by "set_fake_editor" the gold
standard, but isn't a better alternative to make sure that any newly
added tests after this point (or before the commentchar tests, for
that matter) set a fake editor it wants to use explicitly?

> (There are no such tests presently, but a subsequent
> patch will introduce one.)  Fix this problem.
>
> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
> ---
>  t/t3404-rebase-interactive.sh | 1 +
>  1 file changed, 1 insertion(+)
>
> diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
> index 49ccb38..af141be 100755
> --- a/t/t3404-rebase-interactive.sh
> +++ b/t/t3404-rebase-interactive.sh
> @@ -949,6 +949,7 @@ test_expect_success 'rebase -i respects core.commentchar' '
>  	sed -e "2,\$s/^/\\\\/" "$1" >"$1.tmp" &&
>  	mv "$1.tmp" "$1"
>  	EOF
> +	test_when_finished "set_fake_editor" &&
>  	test_set_editor "$(pwd)/remove-all-but-first.sh" &&
>  	git rebase -i B &&
>  	test B = $(git cat-file commit HEAD^ | sed -ne \$p)

Re: [PATCH 2/3] t3404: rebase: interactive: demonstrate short SHA-1 collision

[Junio C Hamano]

Eric Sunshine <sunshine@sunshineco.com> writes:

> The 'todo' sheet for interactive rebase shows abbreviated SHA-1's and
> then performs its operations upon those shortened values. This can lead
> to an abort if the SHA-1 of a reworded or edited commit is no longer
> unique within the abbreviated SHA-1 space and a subsequent SHA-1 in the
> todo list has the same abbreviated value.
>
> For example:
>
>   edit f00dfad first
>   pick badbeef second
>
> If, after editing, the new SHA-1 of "first" is now
> badbeef5ba78983324dff5265c80c4490d5a809a, then the subsequent 'pick
> badbeef second' will fail since badbeef is no longer a unique SHA-1
> abbreviation:
>
>   error: short SHA1 badbeef is ambiguous.
>   fatal: Needed a single revision
>   Invalid commit name: badbeef
>
> Demonstrate this problem with a couple of specially crafted commits
> which initially have distinct abbreviated SHA-1's, but for which the
> abbreviated SHA-1's collide after a simple rewording of the first
> commit's message.
>
> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
> ---
>  t/t3404-rebase-interactive.sh | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
>
> diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
> index af141be..e5ebec6 100755
> --- a/t/t3404-rebase-interactive.sh
> +++ b/t/t3404-rebase-interactive.sh
> @@ -977,4 +977,21 @@ test_expect_success 'rebase -i with --strategy and -X' '
>  	test $(cat file1) = Z
>  '
>  
> +test_expect_success 'short SHA-1 setup' '
> +	test_when_finished "git checkout master" &&
> +	git checkout --orphan collide &&
> +	git rm -rf . &&
> +	unset test_tick &&

This will inconvenience tests added later to these two in the
future.  Oversight, or deliberate act knowing that these two are the
last tests in this script ;-)?

One bad thing is that "unset" loses information so that such future
tests cannot resurrect test_tick and continue on from where the last
test-tick left off.

> +	test_commit collide1 collide &&
> +	test_commit --notick collide2 collide &&
> +	test_commit --notick "collide3 115158b5" collide collide3 collide3
> +'
>
> +test_expect_failure 'short SHA-1 collide' '
> +	test_when_finished "reset_rebase && git checkout master" &&
> +	git checkout collide &&
> +	FAKE_COMMIT_MESSAGE="collide2 815200e" \

;-)

> +	FAKE_LINES="reword 1 2" git rebase -i HEAD~2
> +'
> +
>  test_done

Re: [PATCH 1/3] t3404: restore specialized rebase-editor following commentchar test

[Eric Sunshine]

On Mon, Aug 12, 2013 at 2:28 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Eric Sunshine <sunshine@sunshineco.com> writes:
>
>> At start of script, t3404 installs a specialized test-editor ($EDITOR)
>> upon which many of the interactive rebase tests depend.  Late in t3404,
>> test "rebase -i respects core.commentchar" installs its own custom
>> editor but neglects to restore the specialized editor when finished.
>> This oversight will cause later tests, which require the specialized
>> editor, to fail.
>
> That is not oversight but was deliberately done knowing that it will
> be the last test (and new tests can be added before it).

There is no mention of this being deliberate either in the mailing
list discussion [1] or the commit message (180bad3d1), and other tests
have been added following this one.

[1]: http://thread.gmane.org/gmane.comp.version-control.git/216079

> I think the patch is one way to give _known_ status to later tests
> by declaring the editor installed by "set_fake_editor" the gold
> standard, but isn't a better alternative to make sure that any newly
> added tests after this point (or before the commentchar tests, for
> that matter) set a fake editor it wants to use explicitly?

set_fake_editor is the very first thing done by t3404, and many tests
depend upon this state. It would have been inconsistent for this one
new test to be the exception by having to invoke set_fake_editor
itself, however, I don't mind making the new test more self-contained,
despite the inconsistency. (A later cleanup patch can do the same for
other existing tests.)

Re: [PATCH 2/3] t3404: rebase: interactive: demonstrate short SHA-1 collision

[Eric Sunshine]

On Mon, Aug 12, 2013 at 2:31 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Eric Sunshine <sunshine@sunshineco.com> writes:
>
>> The 'todo' sheet for interactive rebase shows abbreviated SHA-1's and
>> then performs its operations upon those shortened values. This can lead
>> to an abort if the SHA-1 of a reworded or edited commit is no longer
>> unique within the abbreviated SHA-1 space and a subsequent SHA-1 in the
>> todo list has the same abbreviated value.
>>
>> For example:
>>
>>   edit f00dfad first
>>   pick badbeef second
>>
>> If, after editing, the new SHA-1 of "first" is now
>> badbeef5ba78983324dff5265c80c4490d5a809a, then the subsequent 'pick
>> badbeef second' will fail since badbeef is no longer a unique SHA-1
>> abbreviation:
>>
>>   error: short SHA1 badbeef is ambiguous.
>>   fatal: Needed a single revision
>>   Invalid commit name: badbeef
>>
>> Demonstrate this problem with a couple of specially crafted commits
>> which initially have distinct abbreviated SHA-1's, but for which the
>> abbreviated SHA-1's collide after a simple rewording of the first
>> commit's message.
>>
>> Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
>> ---
>>  t/t3404-rebase-interactive.sh | 17 +++++++++++++++++
>>  1 file changed, 17 insertions(+)
>>
>> diff --git a/t/t3404-rebase-interactive.sh b/t/t3404-rebase-interactive.sh
>> index af141be..e5ebec6 100755
>> --- a/t/t3404-rebase-interactive.sh
>> +++ b/t/t3404-rebase-interactive.sh
>> @@ -977,4 +977,21 @@ test_expect_success 'rebase -i with --strategy and -X' '
>>       test $(cat file1) = Z
>>  '
>>
>> +test_expect_success 'short SHA-1 setup' '
>> +     test_when_finished "git checkout master" &&
>> +     git checkout --orphan collide &&
>> +     git rm -rf . &&
>> +     unset test_tick &&
>
> This will inconvenience tests added later to these two in the
> future.  Oversight, or deliberate act knowing that these two are the
> last tests in this script ;-)?
>
> One bad thing is that "unset" loses information so that such future
> tests cannot resurrect test_tick and continue on from where the last
> test-tick left off.

Oversight. The commits were quite deliberately crafted with very
specific commit times, commit messages, trees, and blobs in order to
achieve a conflicting short SHA-1 ("badbeef") at rebase time, so it
was necessary to have test_tick at a known state.

It shouldn't be too much effort to save its value and restore it at
the end of the test.

>> +     test_commit collide1 collide &&
>> +     test_commit --notick collide2 collide &&
>> +     test_commit --notick "collide3 115158b5" collide collide3 collide3
>> +'
>>
>> +test_expect_failure 'short SHA-1 collide' '
>> +     test_when_finished "reset_rebase && git checkout master" &&
>> +     git checkout collide &&
>> +     FAKE_COMMIT_MESSAGE="collide2 815200e" \
>
> ;-)
>
>> +     FAKE_LINES="reword 1 2" git rebase -i HEAD~2
>> +'
>> +
>>  test_done