Merge branch 'ew/rebase' into next

* ew/rebase:
  rebase: error out for NO_PYTHON if they use recursive merge
  Add renaming-rebase test.
  rebase: Allow merge strategies to be used when rebasing
  object-refs: avoid division by zero

4 files changed, 326 insertions, 10 deletions

diff --git a/Documentation/git-rebase.txt b/Documentation/git-rebase.txt
index 08ee4aaba..c339c4525 100644
--- a/Documentation/git-rebase.txt
+++ b/Documentation/git-rebase.txt
@@ -7,7 +7,7 @@ git-rebase - Rebase local commits to a new head
 
 SYNOPSIS
 --------
-'git-rebase' [--onto <newbase>] <upstream> [<branch>]
+'git-rebase' [--merge] [--onto <newbase>] <upstream> [<branch>]
 
 'git-rebase' --continue | --skip | --abort
 
@@ -106,6 +106,24 @@ OPTIONS
 --abort::
 	Restore the original branch and abort the rebase operation.
 
+--skip::
+	Restart the rebasing process by skipping the current patch.
+	This does not work with the --merge option.
+
+--merge::
+	Use merging strategies to rebase.  When the recursive (default) merge
+	strategy is used, this allows rebase to be aware of renames on the
+	upstream side.
+
+-s <strategy>, \--strategy=<strategy>::
+	Use the given merge strategy; can be supplied more than
+	once to specify them in the order they should be tried.
+	If there is no `-s` option, a built-in list of strategies
+	is used instead (`git-merge-recursive` when merging a single
+	head, `git-merge-octopus` otherwise).  This implies --merge.
+
+include::merge-strategies.txt[]
+
 NOTES
 -----
 When you rebase a branch, you are changing its history in a way that
diff --git a/git-rebase.sh b/git-rebase.sh
index e6b57b8ab..b9ce1125d 100755
--- a/git-rebase.sh
+++ b/git-rebase.sh
@@ -34,7 +34,96 @@ When you have resolved this problem run \"git rebase --continue\".
 If you would prefer to skip this patch, instead run \"git rebase --skip\".
 To restore the original branch and stop rebasing run \"git rebase --abort\".
 "
+
+MRESOLVEMSG="
+When you have resolved this problem run \"git rebase --continue\".
+To restore the original branch and stop rebasing run \"git rebase --abort\".
+"
 unset newbase
+strategy=recursive
+do_merge=
+dotest=$GIT_DIR/.dotest-merge
+prec=4
+
+continue_merge () {
+	test -n "$prev_head" || die "prev_head must be defined"
+	test -d "$dotest" || die "$dotest directory does not exist"
+
+	unmerged=$(git-ls-files -u)
+	if test -n "$unmerged"
+	then
+		echo "You still have unmerged paths in your index"
+		echo "did you forget update-index?"
+		die "$MRESOLVEMSG"
+	fi
+
+	if test -n "`git-diff-index HEAD`"
+	then
+		git-commit -C "`cat $dotest/current`"
+	else
+		echo "Previous merge succeeded automatically"
+	fi
+
+	prev_head=`git-rev-parse HEAD^0`
+
+	# save the resulting commit so we can read-tree on it later
+	echo "$prev_head" > "$dotest/`printf %0${prec}d $msgnum`.result"
+	echo "$prev_head" > "$dotest/prev_head"
+
+	# onto the next patch:
+	msgnum=$(($msgnum + 1))
+	printf "%0${prec}d" "$msgnum" > "$dotest/msgnum"
+}
+
+call_merge () {
+	cmt="$(cat $dotest/`printf %0${prec}d $1`)"
+	echo "$cmt" > "$dotest/current"
+	git-merge-$strategy "$cmt^" -- HEAD "$cmt"
+	rv=$?
+	case "$rv" in
+	0)
+		git-commit -C "$cmt" || die "commit failed: $MRESOLVEMSG"
+		;;
+	1)
+		test -d "$GIT_DIR/rr-cache" && git-rerere
+		die "$MRESOLVEMSG"
+		;;
+	2)
+		echo "Strategy: $rv $strategy failed, try another" 1>&2
+		die "$MRESOLVEMSG"
+		;;
+	*)
+		die "Unknown exit code ($rv) from command:" \
+			"git-merge-$strategy $cmt^ -- HEAD $cmt"
+		;;
+	esac
+}
+
+finish_rb_merge () {
+	set -e
+
+	msgnum=1
+	echo "Finalizing rebased commits..."
+	git-reset --hard "`cat $dotest/onto`"
+	end="`cat $dotest/end`"
+	while test "$msgnum" -le "$end"
+	do
+		msgnum=`printf "%0${prec}d" "$msgnum"`
+		printf "%0${prec}d" "$msgnum" > "$dotest/msgnum"
+
+		git-read-tree `cat "$dotest/$msgnum.result"`
+		git-checkout-index -q -f -u -a
+		git-commit -C "`cat $dotest/$msgnum`"
+
+		echo "Committed $msgnum"
+		echo '    '`git-rev-list --pretty=oneline -1 HEAD | \
+					sed 's/^[a-f0-9]\+ //'`
+		msgnum=$(($msgnum + 1))
+	done
+	rm -r "$dotest"
+	echo "All done."
+}
+
 while case "$#" in 0) break ;; esac
 do
 	case "$1" in
@@ -46,17 +135,43 @@ do
 			exit 1
 			;;
 		esac
+		if test -d "$dotest"
+		then
+			prev_head="`cat $dotest/prev_head`"
+			end="`cat $dotest/end`"
+			msgnum="`cat $dotest/msgnum`"
+			onto="`cat $dotest/onto`"
+			continue_merge
+			while test "$msgnum" -le "$end"
+			do
+				call_merge "$msgnum"
+				continue_merge
+			done
+			finish_rb_merge
+			exit
+		fi
 		git am --resolved --3way --resolvemsg="$RESOLVEMSG"
 		exit
 		;;
 	--skip)
+		if test -d "$dotest"
+		then
+			die "--skip is not supported when using --merge"
+		fi
 		git am -3 --skip --resolvemsg="$RESOLVEMSG"
 		exit
 		;;
 	--abort)
-		[ -d .dotest ] || die "No rebase in progress?"
+		if test -d "$dotest"
+		then
+			rm -r "$dotest"
+		elif test -d .dotest
+		then
+			rm -r .dotest
+		else
+			die "No rebase in progress?"
+		fi
 		git reset --hard ORIG_HEAD
-		rm -r .dotest
 		exit
 		;;
 	--onto)
@@ -64,6 +179,23 @@ do
 		newbase="$2"
 		shift
 		;;
+	-M|-m|--m|--me|--mer|--merg|--merge)
+		do_merge=t
+		;;
+	-s=*|--s=*|--st=*|--str=*|--stra=*|--strat=*|--strate=*|\
+		--strateg=*|--strategy=*|\
+	-s|--s|--st|--str|--stra|--strat|--strate|--strateg|--strategy)
+		case "$#,$1" in
+		*,*=*)
+			strategy=`expr "$1" : '-[^=]*=\(.*\)'` ;;
+		1,*)
+			usage ;;
+		*)
+			strategy="$2"
+			shift ;;
+		esac
+		do_merge=t
+		;;
 	-*)
 		usage
 		;;
@@ -75,16 +207,25 @@ do
 done
 
 # Make sure we do not have .dotest
-if mkdir .dotest
+if test -z "$do_merge"
 then
-	rmdir .dotest
-else
-	echo >&2 '
+	if mkdir .dotest
+	then
+		rmdir .dotest
+	else
+		echo >&2 '
 It seems that I cannot create a .dotest directory, and I wonder if you
 are in the middle of patch application or another rebase.  If that is not
 the case, please rm -fr .dotest and run me again.  I am stopping in case
 you still have something valuable there.'
-	exit 1
+		exit 1
+	fi
+else
+	if test -d "$dotest"
+	then
+		die "previous dotest directory $dotest still exists." \
+			'try git-rebase < --continue | --abort >'
+	fi
 fi
 
 # The tree must be really really clean.
@@ -152,6 +293,48 @@ then
 	exit 0
 fi
 
-git-format-patch -k --stdout --full-index "$upstream"..ORIG_HEAD |
-git am --binary -3 -k --resolvemsg="$RESOLVEMSG"
+if test -z "$do_merge"
+then
+	git-format-patch -k --stdout --full-index "$upstream"..ORIG_HEAD |
+	git am --binary -3 -k --resolvemsg="$RESOLVEMSG"
+	exit $?
+fi
+
+if test "@@NO_PYTHON@@" && test "$strategy" = "recursive"
+then
+	die 'The recursive merge strategy currently relies on Python,
+which this installation of git was not configured with.  Please consider
+a different merge strategy (e.g. octopus, resolve, stupid, ours)
+or install Python and git with Python support.'
+
+fi
+
+# start doing a rebase with git-merge
+# this is rename-aware if the recursive (default) strategy is used
+
+mkdir -p "$dotest"
+echo "$onto" > "$dotest/onto"
+prev_head=`git-rev-parse HEAD^0`
+echo "$prev_head" > "$dotest/prev_head"
+
+msgnum=0
+for cmt in `git-rev-list --no-merges "$upstream"..ORIG_HEAD \
+			| perl -e 'print reverse <>'`
+do
+	msgnum=$(($msgnum + 1))
+	echo "$cmt" > "$dotest/`printf "%0${prec}d" $msgnum`"
+done
+
+printf "%0${prec}d" 1 > "$dotest/msgnum"
+printf "%0${prec}d" "$msgnum" > "$dotest/end"
+
+end=$msgnum
+msgnum=1
+
+while test "$msgnum" -le "$end"
+do
+	call_merge "$msgnum"
+	continue_merge
+done
 
+finish_rb_merge
diff --git a/object-refs.c b/object-refs.c
index 8afa2276f..a7d49c60d 100644
--- a/object-refs.c
+++ b/object-refs.c
@@ -127,6 +127,9 @@ void mark_reachable(struct object *obj, unsigned int mask)
 
 	if (!track_object_refs)
 		die("cannot do reachability with object refs turned off");
+	/* nothing to lookup */
+	if (!refs_hash_size)
+		return;
 	/* If we've been here already, don't bother */
 	if (obj->flags & mask)
 		return;
diff --git a/t/t3402-rebase-merge.sh b/t/t3402-rebase-merge.sh
new file mode 100755
index 000000000..d34c6cf6f
--- /dev/null
+++ b/t/t3402-rebase-merge.sh
@@ -0,0 +1,112 @@
+#!/bin/sh
+#
+# Copyright (c) 2006 Junio C Hamano
+#
+
+test_description='git rebase --merge test'
+
+. ./test-lib.sh
+
+if test "$no_python"; then
+	echo "Skipping: no python => no recursive merge"
+	test_done
+	exit 0
+fi
+
+T="A quick brown fox
+jumps over the lazy dog."
+for i in 1 2 3 4 5 6 7 8 9 10
+do
+	echo "$i $T"
+done >original
+
+test_expect_success setup '
+	git add original &&
+	git commit -m"initial" &&
+	git branch side &&
+	echo "11 $T" >>original &&
+	git commit -a -m"master updates a bit." &&
+
+	echo "12 $T" >>original &&
+	git commit -a -m"master updates a bit more." &&
+
+	git checkout side &&
+	(echo "0 $T" ; cat original) >renamed &&
+	git add renamed &&
+	git update-index --force-remove original &&
+	git commit -a -m"side renames and edits." &&
+
+	tr "[a-z]" "[A-Z]" <original >newfile &&
+	git add newfile &&
+	git commit -a -m"side edits further." &&
+
+	tr "[a-m]" "[A-M]" <original >newfile &&
+	rm -f original &&
+	git commit -a -m"side edits once again." &&
+
+	git branch test-rebase side &&
+	git branch test-rebase-pick side &&
+	git branch test-reference-pick side &&
+	git checkout -b test-merge side
+'
+
+test_expect_success 'reference merge' '
+	git merge -s recursive "reference merge" HEAD master
+'
+
+test_expect_success rebase '
+	git checkout test-rebase &&
+	git rebase --merge master
+'
+
+test_expect_success 'merge and rebase should match' '
+	git diff-tree -r test-rebase test-merge >difference &&
+	if test -s difference
+	then
+		cat difference
+		(exit 1)
+	else
+		echo happy
+	fi
+'
+
+test_expect_success 'rebase the other way' '
+	git reset --hard master &&
+	git rebase --merge side
+'
+
+test_expect_success 'merge and rebase should match' '
+	git diff-tree -r test-rebase test-merge >difference &&
+	if test -s difference
+	then
+		cat difference
+		(exit 1)
+	else
+		echo happy
+	fi
+'
+
+test_expect_success 'picking rebase' '
+	git reset --hard side &&
+	git rebase --merge --onto master side^^ &&
+	mb=$(git merge-base master HEAD) &&
+	if test "$mb" = "$(git rev-parse master)"
+	then
+		echo happy
+	else
+		git show-branch
+		(exit 1)
+	fi &&
+	f=$(git diff-tree --name-only HEAD^ HEAD) &&
+	g=$(git diff-tree --name-only HEAD^^ HEAD^) &&
+	case "$f,$g" in
+	newfile,newfile)
+		echo happy ;;
+	*)
+		echo "$f"
+		echo "$g"
+		(exit 1)
+	esac
+'
+
+test_done