[RFC/PATCH] blind rebase --onto

From: Clemens Buchacher <drizzd@aon.at>
Date: Apr 17, 2010, 18:44 UTC
Message-ID: <20100417184433.GA14864@localhost>

Hi,

I know that there have been several discussions about rebase tracking in the past and I admit that I was not following them too closely. So please feel free to flame me if this idea is nothing new or even known to be bad. I appreciate your comments and I will try to get up to speed on this topic as soon as possible.

Clemens

--8<-- We start out with a history like this.

         G subtopic
        /
       E---F topic
      /
 A---B---C---D upstream

After rebasing topic to upstream, subtopic is still based on the old history of topic.

         G subtopic
        /
       E       E'---F' topic
      /       /
 A---B---C---D upstream

If the changes introduced by E' differ from the ones introduced by E in any way, rebase will try to re-apply E on top of F'. This is not useful at all and will almost certainly result in needless conflicts.

This situation is described more verbosely in Section "RECOVERING FROM UPSTREAM REBASE, The hard case" of the git-rebase(1) man page. The suggested solution is to use as upstream the branch subtopic was originally based on, i.e. in this case "rebase --onto topic topic@{1}".

Since the "right" upstream to use could have been any other reflog entry, this approach may require a significant amount of manual digging through the reflog.

This patch introduces an algorithm to search the reflog automatically. It searches the reflog for possible merge bases and chooses the one with the "largest amount of common history".

In the example above, B is the merge base of subtopic and topic, but E is the merge base of subtopic and topic@{1} and is a strict descendant of B, which is why E has more common history with subtopic than B does. Therefore, "rebase --onto topic" does the right thing in this case, and it would still do the right thing if topic had been rewritten multiple times in between.

Note 1: This patch requires some cleanup. The branch to be rebased ($branch) is evaluated only later in the code, which is why I am using HEAD directly.

Note 2: The syntax should probably be something more noisy than "rebase --onto <branch>", at least until this should prove to be useful in many cases.

Signed-off-by: Clemens Buchacher <drizzd@aon.at>
---
 git-rebase.sh |   37 ++++++++++++++++++++++++++++++++-----
 1 files changed, 32 insertions(+), 5 deletions(-)

diff --git a/git-rebase.sh b/git-rebase.sh
index fb4fef7..e1d4cbf 100755
--- a/git-rebase.sh
+++ b/git-rebase.sh
@@ -404,11 +404,38 @@ esac
 
 if test -z "$rebase_root"
 then
-	# The upstream head must be given.  Make sure it is valid.
-	upstream_name="$1"
-	shift
-	upstream=`git rev-parse --verify "${upstream_name}^0"` ||
-	die "invalid upstream $upstream_name"
+	if test $# -ge 1
+	then
+		# The upstream head must be given.  Make sure it is valid.
+		upstream_name="$1"
+		shift
+		upstream=`git rev-parse --verify "${upstream_name}^0"` ||
+		die "invalid upstream $upstream_name"
+	else
+		test -n "$newbase" || usage
+		git rev-parse -q --verify "refs/heads/$newbase" >/dev/null ||
+		git rev-parse -q --verify "refs/remotes/$newbase" >/dev/null ||
+		die "not a branch: $newbase"
+		# Search newbase reflog for commit with the largest common
+		# history. In case of nonlinear history only the first branch
+		# found is followed while any parallel ones are discarded.
+		maxbase=
+		for tip in `git rev-list -g "$newbase"`
+		do
+			if base=$(git merge-base "$tip" HEAD) &&
+				(test -z "$maxbase" ||
+				(test -n "`git rev-list $maxbase..$base`" &&
+				 test -z "`git rev-list $base..$maxbase`"))
+			then
+				maxbase="$base"
+			fi
+		done
+		test -n "$maxbase" ||
+		die "Could not find a merge base for $newbase."
+		say "Using merge base $maxbase."
+		upstream_name="$maxbase"
+		upstream="$maxbase"
+	fi
 	unset root_flag
 	upstream_arg="$upstream_name"
 else

-- 
1.7.0.5.3.ga76e