Re: [PATCH] rebase: be cleverer with rebased upstream branches

On Wed, Feb 16, 2011 at 3:03 AM, Martin von Zweigbergk
[off-list ref] wrote:

quoted

On Tue, 15 Feb 2011, Junio C Hamano wrote:

quoted

Would bisection help to avoid the cost?

I don't think the straight-forward use of bisection would work. If the
history looks something like below, where 'b' is the branch to rebase
and 'u' is the upstream, we have to go through each entry in the
reflog to find u@{3}.


       .-u@{0}
      /
     .---u@{1}
    /
x---y-----u@{2}
    \
     .---u@{3}---b
      \
       .-u@{4}


I have an idea inspired by bisection, Thomas's exponential stride, and
what someone (you?) mentioned the other day about virtual merge
commits. I haven't tried it out, but let me know what you think. I'll
try to explain it using an example only:

Exponential stride phase:
1. candidates={ u@{0} }
  merge-base b $candidates -> y, _not_ in $candidates
2. candidates={ u@{1} u@{2} }
  merge-base b $candidates -> y, _not_ in $candidates
3. candidates={ u@{3} u@{4} u@{5} u@{6} }
  merge-base b $candidates -> u@{3}, in $candidates

Doesn't it indicate that u@{3} is the commit we are looking for? I
haven't found a counterexample...

If this is true the following patch can implement it for git-pull.sh and
git-rebase.sh (sorry if it is space damaged):

diff --git i/git-pull.sh w/git-pull.sh
index 2cdea26..09ef0a9 100755
--- i/git-pull.sh
+++ w/git-pull.sh

@@ -189,14 +189,7 @@ test true = "$rebase" && {

       . git-parse-remote &&
       remoteref="$(get_remote_merge_branch "$@" 2>/dev/null)" &&
       oldremoteref="$(git rev-parse -q --verify "$remoteref")" &&
-       for reflog in $(git rev-list -g $remoteref 2>/dev/null)
-       do
-               if test "$reflog" = "$(git merge-base $reflog $curr_branch)"
-               then
-                       oldremoteref="$reflog"
-                       break
-               fi
-       done
+       oldremoteref=$(git merge-base $curr_branch $oldremoteref $(git
rev-list -g $remoteref 2>/dev/null))