Subject: [RFC/PATCH] blind rebase --onto

From: Clemens Buchacher <[email-masked]>
Date: Sat, 17 Apr 2010 20:44:33 +0200

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 <[email-masked]>
---
 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