[PATCH] Fix rebase -p --onto

[PATCH] Fix rebase -p --onto

[Greg Price]

In a rebase with --onto, the correct test for whether we can skip
rewriting a commit is if it is already on top of $ONTO, not $UPSTREAM.
Without --onto, this distinction does not exist and the behavior does
not change.


In the situation

 X---o---o---o---M
  \             /
   x---x---x---x

 Y

if we try to move the branches merged at M from their base on X to be
based on Y, so as to get

 X

 Y---o'--o'--o'--M'
  \             /
   x'--x'--x'--x'

then we fail.  The command `git rebase -p --onto Y X M` moves only the
first-parent chain, like so:

 X
  \
   x---x---x---x
                \
 Y---o'--o'--o'--M'

because it mistakenly drops the other branch(es) x---x---x---x from
the TODO file.  This tests and fixes this behavior.

Signed-off-by: Greg Price <price@ksplice.com>
Cc: Stephen Haberman <stephen@exigencecorp.com>
---

 git-rebase--interactive.sh      |    2 +-
 t/t3414-rebase-preserve-onto.sh |   48 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 1 deletions(-)
 create mode 100644 t/t3414-rebase-preserve-onto.sh

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index f96d887..23ded48 100755
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -703,7 +703,7 @@ first and then run 'git rebase --continue' again."
 					preserve=t
 					for p in $(git rev-list --parents -1 $sha1 | cut -d' ' -s -f2-)
 					do
-						if test -f "$REWRITTEN"/$p -a \( $p != $UPSTREAM -o $sha1 = $first_after_upstream \)
+						if test -f "$REWRITTEN"/$p -a \( $p != $ONTO -o $sha1 = $first_after_upstream \)
 						then
 							preserve=f
 						fi
diff --git a/t/t3414-rebase-preserve-onto.sh b/t/t3414-rebase-preserve-onto.sh
new file mode 100644
index 0000000..ee29517
--- /dev/null
+++ b/t/t3414-rebase-preserve-onto.sh
@@ -0,0 +1,48 @@
+#!/bin/sh
+#
+# Copyright (c) 2009 Greg Price
+#
+
+test_description='git rebase -p should respect --onto
+
+In a rebase with --onto, we should rewrite all the commits that
+aren'"'"'t on top of $ONTO, even if they are on top of $UPSTREAM.
+'
+. ./test-lib.sh
+
+. ../lib-rebase.sh
+
+# Set up branches like this:
+# A1---B1---D1---E1
+#  \    \        /
+#   \    \--C1--/
+#    F1
+
+test_expect_success 'setup' '
+	test_commit A1 &&
+	test_commit B1 &&
+	test_commit C1 &&
+	git reset --hard B1 &&
+	test_commit D1 &&
+	test_merge E1 C1 &&
+	git reset --hard A1 &&
+	test_commit F1
+'
+
+# Now rebase E1 from B1 onto F1, expect to get this:
+# A1---B1---D1---E1
+#  \    \        /
+#   \    \--C1--/
+#    \
+#     F1---D2---E2
+#      \        /
+#       \--C2--/
+
+test_expect_success 'rebase from B1 onto F1' '
+	git checkout E1 &&
+	git rebase -p --onto F1 B1 &&
+	test "$(git rev-parse HEAD^1^1)" = "$(git rev-parse F1)" &&
+	test "$(git rev-parse HEAD^2^1)" = "$(git rev-parse F1)"
+'
+
+test_done
-- 
1.6.4.rc0.19.gbedf

Re: [PATCH] Fix rebase -p --onto

[Johannes Sixt]

Greg Price schrieb:
> In a rebase with --onto, the correct test for whether we can skip
> rewriting a commit is if it is already on top of $ONTO, not $UPSTREAM.
> Without --onto, this distinction does not exist and the behavior does
> not change.
> 
> 
> In the situation
> 
>  X---o---o---o---M
>   \             /
>    x---x---x---x
> 
>  Y
> 
> if we try to move the branches merged at M from their base on X to be
> based on Y, so as to get
> 
>  X
> 
>  Y---o'--o'--o'--M'
>   \             /
>    x'--x'--x'--x'
> 
> then we fail.  The command `git rebase -p --onto Y X M` moves only the
> first-parent chain, like so:
> 
>  X
>   \
>    x---x---x---x
>                 \
>  Y---o'--o'--o'--M'
> 
> because it mistakenly drops the other branch(es) x---x---x---x from
> the TODO file.  This tests and fixes this behavior.

I think the current behavior is by design. There is nothing to fix.

The purpose of rebase -p is to leave non-first children alone and rebase
only the first child parenthood chain. It is not the purpose to reseat an
entire history DAG.

-- Hannes

Re: [PATCH] Fix rebase -p --onto

[Junio C Hamano]

Johannes Sixt <j.sixt@viscovery.net> writes:

> Greg Price schrieb:
>> In a rebase with --onto, the correct test for whether we can skip
>> rewriting a commit is if it is already on top of $ONTO, not $UPSTREAM.
>> Without --onto, this distinction does not exist and the behavior does
>> not change.
>> 
>> 
>> In the situation
>> 
>>  X---o---o---o---M
>>   \             /
>>    x---x---x---x
>> 
>>  Y
>> ...
>> The command `git rebase -p --onto Y X M` moves only the
>> first-parent chain, like so:
>> 
>>  X
>>   \
>>    x---x---x---x
>>                 \
>>  Y---o'--o'--o'--M'
>> 
>> because it mistakenly drops the other branch(es) x---x---x---x from
>> the TODO file.  This tests and fixes this behavior.
>
> I think the current behavior is by design. There is nothing to fix.
>
> The purpose of rebase -p is to leave non-first children alone and rebase
> only the first child parenthood chain. It is not the purpose to reseat an
> entire history DAG.

Hmm, if the original history were

 .---X---o---o---o---M
  \                 /
   x---x---x---x---x

     Y

and the rebase is about moving history leading to M since X on top of Y,
I would actually have agreed that this

 .---X---o---o---o---M
  \                 /
   x---x---x---x---x
                    \
     Y---o'--o'--o'--M'

would be the right thing to do (IOW, I would agree with you).

Can the current code distinguish the two cases?  More generally, can we
always tell these two cases apart, or is it fundamentally not possible to
differentiate the two cases and we should simplify the problem space by
limiting ourselves by treating the first parent in a special way?

Re: [PATCH] Fix rebase -p --onto

[Johannes Sixt]

Junio C Hamano schrieb:
> Johannes Sixt <j.sixt@viscovery.net> writes:
> 
>> Greg Price schrieb:
>>> In a rebase with --onto, the correct test for whether we can skip
>>> rewriting a commit is if it is already on top of $ONTO, not $UPSTREAM.
>>> Without --onto, this distinction does not exist and the behavior does
>>> not change.
>>>
>>>
>>> In the situation
>>>
>>>  X---o---o---o---M
>>>   \             /
>>>    x---x---x---x
>>>
>>>  Y
>>> ...
>>> The command `git rebase -p --onto Y X M` moves only the
>>> first-parent chain, like so:
>>>
>>>  X
>>>   \
>>>    x---x---x---x
>>>                 \
>>>  Y---o'--o'--o'--M'
>>>
>>> because it mistakenly drops the other branch(es) x---x---x---x from
>>> the TODO file.  This tests and fixes this behavior.
>> I think the current behavior is by design. There is nothing to fix.
>>
>> The purpose of rebase -p is to leave non-first children alone and rebase
>> only the first child parenthood chain. It is not the purpose to reseat an
>> entire history DAG.
> 
> Hmm, if the original history were
> 
>  .---X---o---o---o---M
>   \                 /
>    x---x---x---x---x
> 
>      Y
> 
> and the rebase is about moving history leading to M since X on top of Y,
> I would actually have agreed that this
> 
>  .---X---o---o---o---M
>   \                 /
>    x---x---x---x---x
>                     \
>      Y---o'--o'--o'--M'
> 
> would be the right thing to do (IOW, I would agree with you).
> 
> Can the current code distinguish the two cases?  More generally, can we
> always tell these two cases apart, or is it fundamentally not possible to
> differentiate the two cases and we should simplify the problem space by
> limiting ourselves by treating the first parent in a special way?

I have used rebase -i -p in the past to rewrite history that involves
merges of topic branches like this:

  ---------Y--M--M--F     <-- master
             /  /
  ----a--a--a  /
              /
  --b--b--b--b

where F is a fixup that I want to insert between Y and M, and I thought
rebase -i -p was intended for this use-case.

With this in mind, I do not see why should we distinguish the cases. I
would even go so far to say that this is OK:

  X---a---o---o---M            X---a
       \         /    ===>          \
        x---x---x                    x---x---x
                                              \
  Y                            Y---a'--o'--o'--M'

Re: [PATCH] Fix rebase -p --onto

[Johannes Sixt]

Johannes Sixt schrieb:
> I have used rebase -i -p in the past to rewrite history that involves
> merges of topic branches like this:
> 
>   ---------Y--M--M--F     <-- master
>              /  /
>   ----a--a--a  /
>               /
>   --b--b--b--b
> 
> where F is a fixup that I want to insert between Y and M, and I thought
> rebase -i -p was intended for this use-case.
> 
> With this in mind, I do not see why should we distinguish the cases. I
> would even go so far to say that this is OK:
> 
>   X---a---o---o---M            X---a
>        \         /    ===>          \
>         x---x---x                    x---x---x
>                                               \
>   Y                            Y---a'--o'--o'--M'

because it is a user error: wrong tool for the task. The right tool would
perhaps be git-sequencer.

-- Hannes
(I hit the send button too early by accident, sorry for the excessive
quoting in the previous mail.)

Re: [PATCH] Fix rebase -p --onto

[Greg Price]

On Fri, Jul 17, 2009 at 01:27:46AM -0700, Junio C Hamano wrote:
> Hmm, if the original history were
> 
>  .---X---o---o---o---M
>   \                 /
>    x---x---x---x---x
> 
>      Y
> 
> and the rebase is about moving history leading to M since X on top of Y,
> I would actually have agreed that this
> 
>  .---X---o---o---o---M
>   \                 /
>    x---x---x---x---x
>                     \
>      Y---o'--o'--o'--M'
> 
> would be the right thing to do (IOW, I would agree with you).

Yes, I agree.


> Can the current code distinguish the two cases?

Yes.  Stephen's commit acc8559 already limits $TODO to the descendants
of the merge-bases of HEAD and UPSTREAM, which captures the
distinction here.  When we rebase from X, the merge-base is X, so only
that branch moves.  When we rebase from the base of both branches,
both branches should move.

I've added a test demonstrating this case to a revised version of the
patch, below.

Greg



>From dcab1103e14394364c15136823269416f8c56e97 Mon Sep 17 00:00:00 2001
From: Greg Price <price@ksplice.com>
Date: Thu, 16 Jul 2009 12:48:40 -0400
Subject: [PATCH] Fix rebase -p --onto

In a rebase with --onto, the correct test for whether we can skip
rewriting a commit is if it is already on top of $ONTO, not $UPSTREAM.
Without --onto, this distinction does not exist and the behavior does
not change.

In the situation

 X---o---o---o---M
  \             /
   x---x---x---x

 Y

if we try to move the branches merged at M from their base on X to be
based on Y, so as to get

 X

 Y---o'--o'--o'--M'
  \             /
   x'--x'--x'--x'

then we fail.  The command `git rebase -p --onto Y X M` moves only the
first-parent chain, like so:

 X
  \
   x---x---x---x
                \
 Y---o'--o'--o'--M'

because it mistakenly drops the other branch(es) x---x---x---x from
the TODO file.  This tests and fixes this behavior.

Signed-off-by: Greg Price <price@ksplice.com>
---
 git-rebase--interactive.sh      |    2 +-
 t/t3414-rebase-preserve-onto.sh |   80 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 81 insertions(+), 1 deletions(-)
 create mode 100755 t/t3414-rebase-preserve-onto.sh

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index f96d887..23ded48 100755
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -703,7 +703,7 @@ first and then run 'git rebase --continue' again."
 					preserve=t
 					for p in $(git rev-list --parents -1 $sha1 | cut -d' ' -s -f2-)
 					do
-						if test -f "$REWRITTEN"/$p -a \( $p != $UPSTREAM -o $sha1 = $first_after_upstream \)
+						if test -f "$REWRITTEN"/$p -a \( $p != $ONTO -o $sha1 = $first_after_upstream \)
 						then
 							preserve=f
 						fi
diff --git a/t/t3414-rebase-preserve-onto.sh b/t/t3414-rebase-preserve-onto.sh
new file mode 100755
index 0000000..80019ee
--- /dev/null
+++ b/t/t3414-rebase-preserve-onto.sh
@@ -0,0 +1,80 @@
+#!/bin/sh
+#
+# Copyright (c) 2009 Greg Price
+#
+
+test_description='git rebase -p should respect --onto
+
+In a rebase with --onto, we should rewrite all the commits that
+aren'"'"'t on top of $ONTO, even if they are on top of $UPSTREAM.
+'
+. ./test-lib.sh
+
+. ../lib-rebase.sh
+
+# Set up branches like this:
+# A1---B1---E1---F1---G1
+#  \    \             /
+#   \    \--C1---D1--/
+#    H1
+
+test_expect_success 'setup' '
+	test_commit A1 &&
+	test_commit B1 &&
+	test_commit C1 &&
+	test_commit D1 &&
+	git reset --hard B1 &&
+	test_commit E1 &&
+	test_commit F1 &&
+	test_merge G1 D1 &&
+	git reset --hard A1 &&
+	test_commit H1
+'
+
+# Now rebase merge G1 from both branches' base B1, both should move:
+# A1---B1---E1---F1---G1
+#  \    \             /
+#   \    \--C1---D1--/
+#    \
+#     H1---E2---F2---G2
+#      \             /
+#       \--C2---D2--/
+
+test_expect_success 'rebase from B1 onto H1' '
+	git checkout G1 &&
+	git rebase -p --onto H1 B1 &&
+	test "$(git rev-parse HEAD^1^1^1)" = "$(git rev-parse H1)" &&
+	test "$(git rev-parse HEAD^2^1^1)" = "$(git rev-parse H1)"
+'
+
+# On the other hand if rebase from E1 which is within one branch,
+# then the other branch stays:
+# A1---B1---E1---F1---G1
+#  \    \             /
+#   \    \--C1---D1--/
+#    \             \
+#     H1-----F3-----G3
+
+test_expect_success 'rebase from E1 onto H1' '
+	git checkout G1 &&
+	git rebase -p --onto H1 E1 &&
+	test "$(git rev-parse HEAD^1^1)" = "$(git rev-parse H1)" &&
+	test "$(git rev-parse HEAD^2)" = "$(git rev-parse D1)"
+'
+
+# And the same if we rebase from a commit in the second-parent branch.
+# A1---B1---E1---F1----G1
+#  \    \          \   /
+#   \    \--C1---D1-\-/
+#    \               \
+#     H1------D3------G4
+
+test_expect_success 'rebase from C1 onto H1' '
+	git checkout G1 &&
+	git rev-list --first-parent --pretty=oneline C1..G1 &&
+	git rebase -p --onto H1 C1 &&
+	test "$(git rev-parse HEAD^2^1)" = "$(git rev-parse H1)" &&
+	test "$(git rev-parse HEAD^1)" = "$(git rev-parse F1)"
+'
+
+test_done
-- 
1.6.3.1.499.ge7b8da

Re: [PATCH] Fix rebase -p --onto

[Greg Price]

On Fri, Jul 17, 2009 at 10:40:08AM +0200, Johannes Sixt wrote:
> I have used rebase -i -p in the past to rewrite history that involves
> merges of topic branches like this:
> 
>   ---------Y--M--M--F     <-- master
>              /  /
>   ----a--a--a  /
>               /
>   --b--b--b--b
> 
> where F is a fixup that I want to insert between Y and M, and I thought
> rebase -i -p was intended for this use-case.

I don't believe rebase -i -p has ever worked with reordering commits.
It certainly doesn't now, as the tests below demonstrate both for your
case and for the most trivial possible situation without even any merges.

This is not a mere coding error, as in the general case with a hairy
set of merges it's not clear what an arbitrary reordering of the
commits would even mean.  To really fix it will require a richer TODO
file format, as in the sequencer or the discussion Johannes Schindelin
started in January about a rebase -i -p rework.


In any case, this has nothing to do with my patch to fix -p --onto,
which is a no-op when --onto is not used.  You want `git rebase -i -p Y`,
and the generation of the TODO file correctly gives you M, M, F.
It's the execution of the TODO file you give back, with F, M, M,
that does not do what you want.

Cheers,
Greg



>From 185fa9da4caee5a0a96105e60269d02ec832e876 Mon Sep 17 00:00:00 2001
From: Greg Price <price@ksplice.com>
Date: Fri, 17 Jul 2009 11:55:11 -0400
Subject: [PATCH] Add failing test for commit reordering in rebase -i -p

Signed-off-by: Greg Price <price@ksplice.com>
---
 t/t3411-rebase-preserve-around-merges.sh |   59 ++++++++++++++++++++++++++++++
 1 files changed, 59 insertions(+), 0 deletions(-)

diff --git a/t/t3411-rebase-preserve-around-merges.sh b/t/t3411-rebase-preserve-around-merges.sh
index 6533505..1759a98 100755
--- a/t/t3411-rebase-preserve-around-merges.sh
+++ b/t/t3411-rebase-preserve-around-merges.sh
@@ -71,4 +71,63 @@ test_expect_success 'rebase two levels of merge' '
 	test "$(git rev-parse HEAD^2^1^1)" = "$(git rev-parse HEAD^2^2^1)"
 '
 
+# Reorder commits while using -p.  Basic prerequisite for the next test
+# to have a hope of working.
+#
+# a---b---c
+#
+# want
+#
+# a---c---b
+
+test_expect_failure 'reorder with -p' '
+	test_commit a &&
+	test_commit b &&
+	test_commit c &&
+	FAKE_LINES="2 1" git rebase -i -p HEAD~2 &&
+	test "$(git rev-parse HEAD~2)" = "$(git rev-parse a)" &&
+	git log -n1 --pretty=format:%s HEAD | grep b &&
+	git log -n1 --pretty=format:%s HEAD^ | grep c
+'
+
+
+# Reorder a commit to before a merge.  From
+#
+# R---x---Ma--Mb--F
+#  \     /   /
+#   a1--a2  /
+#    \     /
+#     b1--b2
+#
+# we get
+#
+# R---x---F*--Ma*--Mb*
+#  \         /    /
+#   a1--a2--/    /
+#    \          /
+#     b1--b2---/
+
+test_expect_failure 'rewrite to before merge' '
+	test_commit R &&
+	test_commit a1 &&
+	test_commit b1 &&
+	test_commit b2 &&
+	git reset --hard a1 &&
+	test_commit a2 &&
+	git reset --hard R &&
+	test_commit x &&
+	test_merge Ma a2 &&
+	test_merge Mb b2 &&
+	test_commit F &&
+
+	FAKE_LINES="3 1 2" git rebase -i -p x &&
+	git log --pretty=oneline HEAD && echo &&
+	git log --pretty=oneline HEAD^2 && echo &&
+	git log --pretty=oneline HEAD^^2 && echo &&
+	git log --pretty=oneline HEAD^^ && echo &&
+	test "$(git rev-parse HEAD^2)" = "$(git rev-parse b2)" &&
+	test "$(git rev-parse HEAD^1^2)" = "$(git rev-parse a2)" &&
+	test "$(git rev-parse HEAD~3)" = "$(git rev-parse x)"
+'
+
 test_done
-- 
1.6.3.1.499.ge7b8da

Re: [PATCH] Fix rebase -p --onto

[Johannes Schindelin]

Hi,

On Fri, 17 Jul 2009, Greg Price wrote:

> On Fri, Jul 17, 2009 at 10:40:08AM +0200, Johannes Sixt wrote:
> > I have used rebase -i -p in the past to rewrite history that involves
> > merges of topic branches like this:
> > 
> >   ---------Y--M--M--F     <-- master
> >              /  /
> >   ----a--a--a  /
> >               /
> >   --b--b--b--b
> > 
> > where F is a fixup that I want to insert between Y and M, and I thought
> > rebase -i -p was intended for this use-case.
> 
> I don't believe rebase -i -p has ever worked with reordering commits.

It was not meant to.  Actually, it was never meant as "rebase -i -p", but 
always as "rebase -p" (which, for technical reasons, would be implemented 
in git-rebase--interactive.sh).

Having said that, I am working on a rebase-i-p series which _does_ allow 
reordering commits, putting commits on newly-created topic branches, 
redoing merges explicitely.

Unfortunately, I seem to have less and less time for Git (which is not 
helped by the frustrating experience of a first-slow then-failing GSoC 
project), and when I finally decided to set aside some time to polish the 
series and submit it, 1.6.4-rc0 came out.  And I do not want Junio to be 
distracted from that very important (think push-to-current-branch) 
release.

Ciao,
Dscho

Re: [PATCH] Fix rebase -p --onto

[Greg Price]

On Fri, Jul 17, 2009 at 08:32:20PM +0200, Johannes Schindelin wrote:
> > I don't believe rebase -i -p has ever worked with reordering commits.
> 
> It was not meant to.  Actually, it was never meant as "rebase -i -p", but 
> always as "rebase -p" (which, for technical reasons, would be implemented 
> in git-rebase--interactive.sh).

Understood.  The -p functionality is invaluable already without -i,
and reordering commits with -p raises substantial new questions about
what the behavior should be.

I wonder if it might be worth giving an error message when the user
attempts to reorder commits under -p?  The current behavior is
surprising (reordering A after B, C, D causes B, C, D to be dropped)
even when no merges are involved.  I wouldn't want to give an error on
just the combination of options -i -p, though, since "edit" is useful.


> Having said that, I am working on a rebase-i-p series which _does_ allow 
> reordering commits, putting commits on newly-created topic branches, 
> redoing merges explicitely.

That would be excellent.  I'm using git-sequencer from Stephan Beyer's
seq-builtin-dev branch for some work because I need this kind of
functionality.  It would be great to see it in mainline in one form or
another.  I don't doubt that it will require a good deal of work.

Thanks!
Greg