[BUG] multi-commit cherry-pick messes up the order of commits

Hi,

I did some multi-commit cherry-picks lately, and noticed that
sometimes cherry-pick applied the commits in different order than I
specified on the command line.  After some debugging, today I could
finally come up with a receipe to reproduce:

  git init
  echo 1 >a && git add a
  git commit -m a
  echo 2 >b && git add b
  git commit -m b
  sleep 2 && echo 3 >c && git add c
  git commit -m c
  git checkout -b branch HEAD^^
  git cherry-pick master master^    # the later commit first

where the 'git cherry-pick' command produces the following output:

[branch ef5b86e0] b
 1 files changed, 1 insertions(+), 0 deletions(-)
 create mode 100644 b
[branch 6a74f934] c
 1 files changed, 1 insertions(+), 0 deletions(-)
 create mode 100644 c

Notice that master^, i.e. the commit adding the file 'b', is picked
before master, i.e. the commit adding 'c', although the order on the
command line was the reverse.

This is because

  cmd_cherry_pick()
    pick_revisions()
      walk_revs_populate_todo()
        prepare_revs()

calls prepare_revision_walk(), which parses the commits from the
command line in the order they were specified, but inserts them into a
list ordered by date, and commits will be picked in the order they
appear in this list.  So if you specify commits in a different order
than their committer date or commits with the same commiter date
(which are often produced by am, rebase, and multi-commit
cherry-pick), then they will be picked in wrong order.

As far as I can tell, this buggy behavior is as old as multi-commit
cherry-pick itself, i.e. 7e2bfd3f (revert: allow cherry-picking more
than one commit, 2010-06-02).


Best,
Gábor

Hi all,

2012/1/11 SZEDER Gábor [off-list ref]:

As far as I can tell, this buggy behavior is as old as multi-commit
cherry-pick itself, i.e. 7e2bfd3f (revert: allow cherry-picking more
than one commit, 2010-06-02).

Thanks for the very detailed report!

I didn't test nor even compiled anything but maybe this can be fixed
by adding something like:

opts->revs->topo_order = 1;

in parse_args() or in prepare_revs()

I will try to have a look tonight.

Thanks again,
Christian.

Hi,


On Thu, Jan 12, 2012 at 02:31:30PM +0100, Christian Couder wrote:

Hi all,

2012/1/11 SZEDER Gábor [off-list ref]:

quoted

As far as I can tell, this buggy behavior is as old as multi-commit
cherry-pick itself, i.e. 7e2bfd3f (revert: allow cherry-picking more
than one commit, 2010-06-02).

Thanks for the very detailed report!

I didn't test nor even compiled anything but maybe this can be fixed
by adding something like:

opts->revs->topo_order = 1;

in parse_args() or in prepare_revs()

I will try to have a look tonight.

[Beware, I'm mostly clueless about git internals.]

I don't think that any commit reordering, whether it's based on
committer date, topology, or whatever, is acceptable.  Commits must be
picked in the exact order they are specified on the command line.

Besides, AFAICT, parse_args() sets opts->revs->no_walk = 1, which will
cause prepare_revision_walk() to return before it would reach the
topo_order condition, so opts->revs->topo_order = 1 wouldn't have any
effect.


Best,
Gábor

Hi Gábor,

SZEDER Gábor wrote:

I don't think that any commit reordering, whether it's based on
committer date, topology, or whatever, is acceptable.  Commits must be
picked in the exact order they are specified on the command line.

Thanks for the excellent report.  I'm trying to figure out how to get
the revision API to do no ordering.

-- Ram

On Thu, Jan 12, 2012 at 03:44:09PM +0100, SZEDER Gábor wrote:

quoted

Thanks for the very detailed report!

I didn't test nor even compiled anything but maybe this can be fixed
by adding something like:

opts->revs->topo_order = 1;

in parse_args() or in prepare_revs()

I will try to have a look tonight.

[Beware, I'm mostly clueless about git internals.]

I don't think that any commit reordering, whether it's based on
committer date, topology, or whatever, is acceptable.  Commits must be
picked in the exact order they are specified on the command line.

I thought the multi-commit cherry-pick was supposed to take arbitrary
revision arguments, so you can do:

  git cherry-pick master..topic

and likewise you can spell it:

  git cherry-pick topic ^master

or:

  git cherry-pick ^master topic

So the order of arguments isn't relevant in those cases; the graph
ordering is. I agree it would be nice to make:

  git cherry-pick commit1 commit3 commit2

work in the order specified, but how does that interact with existing
cases that provide more traditional revision arguments?

-Peff

Hi Peff,

Jeff King wrote:

                 I agree it would be nice to make:
 git cherry-pick commit1 commit3 commit2

work in the order specified, but how does that interact with existing
cases that provide more traditional revision arguments?

What are your thoughts on making it a flag in the revision API to be
activated with "cherry-pick --literal-order commit1 commit3 commit2"
or similar?  I'm not sure how to get it to reconcile with the more
traditional revision arguments yet. My current worktree (WIP):

diff --git a/builtin/revert.c b/builtin/revert.c
index 0d8020c..47da41b 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c

@@ -228,6 +228,7 @@ static void parse_args(int argc, const char

**argv, struct re
                opts->revs = xmalloc(sizeof(*opts->revs));
                init_revisions(opts->revs, NULL);
                opts->revs->no_walk = 1;
+               opts->revs->literal_order = 1;
                if (argc < 2)
                        usage_with_options(usage_str, options);
                argc = setup_revisions(argc, argv, opts->revs, NULL);

diff --git a/revision.c b/revision.c
index 064e351..301ef58 100644
--- a/revision.c
+++ b/revision.c

@@ -2054,7 +2054,10 @@ int prepare_revision_walk(struct rev_info *revs)
                if (commit) {
                        if (!(commit->object.flags & SEEN)) {
                                commit->object.flags |= SEEN;
-                               commit_list_insert_by_date(commit,

&revs->commits
+                               if (revs->literal_order)
+                                       commit_list_insert(commit,
&revs->commits
+                               else
+
commit_list_insert_by_date(commit, &revs-
                        }
                }
                e++;

diff --git a/revision.h b/revision.h
index b8e9223..65c3dc3 100644
--- a/revision.h
+++ b/revision.h

@@ -67,6 +67,7 @@ struct rev_info {
                        remove_empty_trees:1,
                        simplify_history:1,
                        lifo:1,
+                       literal_order:1,
                        topo_order:1,
                        simplify_merges:1,
                        simplify_by_decoration:1,

On Thu, Jan 12, 2012 at 10:39:48PM +0530, Ramkumar Ramachandra wrote:

Jeff King wrote:

quoted

                 I agree it would be nice to make:
 git cherry-pick commit1 commit3 commit2

work in the order specified, but how does that interact with existing
cases that provide more traditional revision arguments?

What are your thoughts on making it a flag in the revision API to be
activated with "cherry-pick --literal-order commit1 commit3 commit2"
or similar?  I'm not sure how to get it to reconcile with the more
traditional revision arguments yet. My current worktree (WIP):

I think that is a sensible first-cut. It may even be possible to use
heuristics to identify when --literal-order is needed, and eventually it
could go away. But that is a much riskier feature that can be built on
top of the much safer proposal you are making.

My only concern is that there are other parts of the revision machinery
that depend on the date-ordering of the commit list. What would happen,
for example, with:

  git rev-list --literal-order --do-walk foo

It probably doesn't make sense to allow literal-order without no-walk,
anyway (which of course is the default in cherry-pick anyway, so it's
not a big deal here).

I'm also not sure what:

  git rev-list --literal-order foo..bar

would or should do.

-Peff

Ramkumar Ramachandra wrote:

My current worktree (WIP):
[...]

Classic whitespace breakage.  How many times am I going to fall for
the same joke?

diff --git a/builtin/revert.c b/builtin/revert.c
index 0d8020c..47da41b 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c

@@ -228,6 +228,7 @@ static void parse_args(int argc, const char **argv, struct replay_opts *opts)
 		opts->revs = xmalloc(sizeof(*opts->revs));
 		init_revisions(opts->revs, NULL);
 		opts->revs->no_walk = 1;
+		opts->revs->literal_order = 1;
 		if (argc < 2)
 			usage_with_options(usage_str, options);
 		argc = setup_revisions(argc, argv, opts->revs, NULL);

diff --git a/revision.c b/revision.c
index 064e351..301ef58 100644
--- a/revision.c
+++ b/revision.c

@@ -2054,7 +2054,10 @@ int prepare_revision_walk(struct rev_info *revs)
 		if (commit) {
 			if (!(commit->object.flags & SEEN)) {
 				commit->object.flags |= SEEN;
-				commit_list_insert_by_date(commit, &revs->commits);
+				if (revs->literal_order)
+					commit_list_insert(commit, &revs->commits);
+				else
+					commit_list_insert_by_date(commit, &revs->commits);
 			}
 		}
 		e++;

diff --git a/revision.h b/revision.h
index b8e9223..65c3dc3 100644
--- a/revision.h
+++ b/revision.h

@@ -67,6 +67,7 @@ struct rev_info {
 			remove_empty_trees:1,
 			simplify_history:1,
 			lifo:1,
+			literal_order:1,
 			topo_order:1,
 			simplify_merges:1,
 			simplify_by_decoration:1,

Hi Peff,

Jeff King wrote:

It may even be possible to use
heuristics to identify when --literal-order is needed, and eventually it
could go away.

Yeah, that would be really nice.

My only concern is that there are other parts of the revision machinery
that depend on the date-ordering of the commit list.

Agreed.  Looking at it another way, it's an opportunity to read
revision.c, learn, and modernize some older parts :)

What would happen,
for example, with:

 git rev-list --literal-order --do-walk foo

It probably doesn't make sense to allow literal-order without no-walk,
anyway (which of course is the default in cherry-pick anyway, so it's
not a big deal here).

I don't know if that particular case is a problem: there are some
mutually exclusive options in revision.c already like:

  cannot combine --reverse with --graph

This'll just be another one of them.

I'm also not sure what:

 git rev-list --literal-order foo..bar

would or should do.

Instead of classifying it as an "ordering" option (as defined in
Documentation/rev-list-options.txt), I think we should give it some
sort of special status for now -- it can be combined with ordering
options (of which date ordering is default anyway).  For this specific
question, I suspect that revision.c does a topo-ordering for commit
ranges (I haven't read the code), so we have to make sure that
whatever extra logic we add doesn't disrupt the existing logic in
revision.c.

-- Ram

Jeff King wrote:

I agree it would be nice to make:

  git cherry-pick commit1 commit3 commit2

work in the order specified, but how does that interact with existing
cases that provide more traditional revision arguments?

Yes, exactly.  Another question: what should

	git cherry-pick master..next maint..master

do?

Due to the way traditional revision arguments work, the following
invocations of 'git cherry-pick' are equivalent:

  $ git cherry-pick master..topic
  $ git cherry-pick topic ^master
  $ git cherry-pick ^master topic

So the order of the arguments specified on the command-line is
irrelevant in these cases.  However, there are cases where it is worth
paying attention to the order.  For instance:

  $ git cherry-pick commit3 commit1 commit2

picks commits after sorting by date order, which is counter-intuitive.
Add a failing test to t3508 (cherry-pick-many-commits) documenting
this behavior.

Reported-by: SZEDER Gábor <redacted>
Signed-off-by: Ramkumar Ramachandra <redacted>
---
 Irrespective of how far we get with the '--literal-order' idea, I
 think this quirk is worth documenting.

 t/t3508-cherry-pick-many-commits.sh |   25 +++++++++++++++++++++++++
 1 files changed, 25 insertions(+), 0 deletions(-)

diff --git a/t/t3508-cherry-pick-many-commits.sh b/t/t3508-cherry-pick-many-commits.sh
index 8e09fd0..dd65835 100755
--- a/t/t3508-cherry-pick-many-commits.sh
+++ b/t/t3508-cherry-pick-many-commits.sh

@@ -59,6 +59,31 @@ test_expect_success 'cherry-pick first..fourth works' '
 	check_head_differs_from fourth
 '
 
+test_expect_failure 'cherry-pick picks commits in the right order' '
+	cat <<-\EOF >expected &&
+	[master OBJID] fourth
+	 Author: A U Thor <author@example.com>
+	 1 files changed, 1 insertions(+), 0 deletions(-)
+	[master OBJID] second
+	 Author: A U Thor <author@example.com>
+	 1 files changed, 1 insertions(+), 0 deletions(-)
+	[master OBJID] third
+	 Author: A U Thor <author@example.com>
+	 1 files changed, 1 insertions(+), 0 deletions(-)
+	EOF
+
+	git checkout -f master &&
+	git reset --hard first &&
+	test_tick &&
+	git cherry-pick fourth second third >actual &&
+	git diff --quiet other &&
+	git diff --quiet HEAD other &&
+
+	sed -e "s/$_x05[0-9a-f][0-9a-f]/OBJID/" <actual >actual.fuzzy &&
+	test_cmp expected actual.fuzzy &&
+	check_head_differs_from second
+'
+
 test_expect_success 'cherry-pick --strategy resolve first..fourth works' '
 	cat <<-\EOF >expected &&
 	Trying simple merge.

-- 
1.7.8.2

Ramkumar Ramachandra wrote:

  $ git cherry-pick master..topic
  $ git cherry-pick topic ^master
  $ git cherry-pick ^master topic

So the order of the arguments specified on the command-line is
irrelevant in these cases.  However, there are cases where it is worth
paying attention to the order.  For instance:

This segue feels a bit unnatural.  I think the relevant point was that
early output from revision traversal (and perhaps some other things

--- I haven't checked) relies on commits having been inserted in a

topologically sorted order.

Anyway, I don't think the background is necessary --- the
one-paragraph description below stands well enough alone.

  $ git cherry-pick commit3 commit1 commit2

picks commits after sorting by date order, which is counter-intuitive.
Add a failing test to t3508 (cherry-pick-many-commits) documenting
this behavior.

Reported-by: SZEDER Gábor <redacted>
Signed-off-by: Ramkumar Ramachandra <redacted>
---

[...]

I would say "in the order requested" instead of the right order, since
it is not completely obvious to me what the right order is.

+	cat <<-\EOF >expected &&
+	[master OBJID] fourth
+	 Author: A U Thor [off-list ref]
+	 1 files changed, 1 insertions(+), 0 deletions(-)
+	[master OBJID] second
+	 Author: A U Thor [off-list ref]
+	 1 files changed, 1 insertions(+), 0 deletions(-)
+	[master OBJID] third
+	 Author: A U Thor [off-list ref]
+	 1 files changed, 1 insertions(+), 0 deletions(-)
+	EOF

Why check all these details of formatting, instead of e.g. using "git
rev-list | git diff-tree -s --format=%s"?

[...]

+	test_cmp expected actual.fuzzy &&
+	check_head_differs_from second

Why make the same check twice?

Hope that helps,
Jonathan

The invocation

  $ git cherry-pick commit3 commit1 commit2

picks commits after sorting by date order, which is counter-intuitive.
Add a failing test to t3508 (cherry-pick-many-commits) documenting
this behavior.

Signed-off-by: Ramkumar Ramachandra <redacted>
---
 Had some weird compulsion to conform to the style of the other tests
 in the previous iteration.

 t/t3508-cherry-pick-many-commits.sh |   17 +++++++++++++++++
 1 files changed, 17 insertions(+), 0 deletions(-)

diff --git a/t/t3508-cherry-pick-many-commits.sh b/t/t3508-cherry-pick-many-commits.sh
index 8e09fd0..d9d632d 100755
--- a/t/t3508-cherry-pick-many-commits.sh
+++ b/t/t3508-cherry-pick-many-commits.sh

@@ -59,6 +59,23 @@ test_expect_success 'cherry-pick first..fourth works' '
 	check_head_differs_from fourth
 '
 
+test_expect_failure 'cherry-pick picks commits in the order requested' '
+	git checkout -f master &&
+	git reset --hard first &&
+	test_tick &&
+	git cherry-pick fourth second third &&
+	{
+		git rev-list --reverse HEAD |
+		git diff-tree --stdin -s --format=%s
+	} >actual &&
+	cat >expect <<-\EOF &&
+	fourth
+	second
+	third
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'cherry-pick --strategy resolve first..fourth works' '
 	cat <<-\EOF >expected &&
 	Trying simple merge.

-- 
1.7.8.2

Am 12.01.2012 18:09, schrieb Ramkumar Ramachandra:

Why do we need a new flag?

  git show origin/master origin/maint
  git show origin/maint origin/master

show the revisions in different order, in particular, in the order
requested on the command line. Shoudn't cherry-pick be able to do the
same without new hacks?

-- Hannes

Hi Johannes,

Johannes Sixt wrote:

Why do we need a new flag?

 git show origin/master origin/maint
 git show origin/maint origin/master

show the revisions in different order, in particular, in the order
requested on the command line. Shoudn't cherry-pick be able to do the
same without new hacks?

That was my first reaction too -- then I saw builtin/push.c (the
builtin show is quite similar), and found out that it doesn't use the
revision walker at all.  It operates on refs, which has different
semantics altogether (called "refspec" in some places I think).

-- Ram

Ramkumar Ramachandra wrote:

 Had some weird compulsion to conform to the style of the other tests
 in the previous iteration.

The tests you're talking about were introduced in commit 7b53b92f to
check for a buglet that made --strategy suppress the progress
reporting ("Finished one cherry-pick.") output cherry-pick normally
would emit.  

So no inconsistency here --- those tests are _intending_ to check the
output format and that cherry-pick, unlike cherry-pick --ff, produces
new commits (though it would probably be clearer to put checks for
these behaviors in separate test assertions), while the new failing
test you are introducing is not about those things.

Striving for a consistent style is certainly not weird.

[...]

+	git cherry-pick fourth second third &&
+	{
+		git rev-list --reverse HEAD |
+		git diff-tree --stdin -s --format=%s
+	} >actual &&
+	cat >expect <<-\EOF &&
+	fourth
+	second
+	third
+	EOF
+	test_cmp expect actual

This still feels more convoluted than expected (e.g., why --reverse?).
Something like

	printf "%s\n" third second fourth >expect &&
	...
	git log --format=%s >actual &&
	test_cmp expect actual

should be plenty.

Ramkumar Ramachandra wrote:

That was my first reaction too -- then I saw builtin/push.c (the
builtin show is quite similar), and found out that it doesn't use the
revision walker at all.

"git push", unlike "git show", does not accept arguments like
maint..master.