[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 <szeder@ira.uka.de>:

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:

[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:

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:

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:

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):

Ramkumar Ramachandra wrote:

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

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

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

Hi Peff,

Jeff King wrote:

Yeah, that would be really nice.

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

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.

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

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 <szeder@ira.uka.de>
Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
---
 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(-)

Ramkumar Ramachandra wrote:

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.

[...]

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.

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

[...]

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 <artagnon@gmail.com>
---
 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(-)

Ramkumar Ramachandra wrote:

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.

[...]

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 <artagnon@gmail.com> writes:

That is an insane UI for the sake of flexibility.

You should be able to look at revs->cmdline and tell if you need to let cherry-pick walk (i.e. "cherry-pick master..next"), or if the user wants individual commits (i.e. "cherry-pick A B C").

And you do prepare_revision_walk() only when you need to walk; otherwise you use the contents of revs->pending in order.

Junio C Hamano wrote:

Okay, just to make sure I understand this correctly: if more than one argument is literally specified, I should not set up the revision walker and pick the commits listed in revs->pending, correct? Then, when I encounter the following command,

  $ git cherry-pick maint ^master

I should just pick two commits: maint, and ^master. But won't this introduce some kind of regression for those who expect me to pick the master..maint range instead? Has this double-interpretation issue come up in other commands? Have we documented this somewhere?

Thanks.

-- Ram

On Fri, Jan 13, 2012 at 12:55:58AM +0530, Ramkumar Ramachandra wrote:

I am tempted to suggest that cherry-pick should not feed its arguments to the revision machinery in the first place, but instead accept a set of arguments, each argument of which is either a single commit (interpreted by get_sha1) or a range specifier (which can be fed to setup-revisions). And then get a linearized set of commits for _each_ argument independently and concatenate them (possibly eliminating duplicates). That would make all of these work as most people would expect:

  git cherry-pick A B C
  git cherry-pick A..B
  git cherry-pick A..B B..C

but would be a regression for:

  git cherry-pick B ^A

versus the current code. I suspect that the latter form is not all that commonly used, though, and certainly I would accept it as a casualty of making the "A B C" form work. My only hesitation is that it is in fact a regression.

But ^master is not a commit, it is a negation. So it is nonsensical if the arguments are considered independent of each other (you _could_ use a heuristic to guess that they are not independent, but I'd rather not go there). So you'd probably end up just rejecting the arguments.

-Peff

Jeff King wrote:

[...]

I find myself using such complicated expressions as

	list-revs-to-skip |
	xargs git cherry-pick --cherry-pick --right-only HEAD...topic --not

so yeah, that would be a pretty serious loss in functionality.

However, moving to something like the far future semantics that Junio hinted at, for cherry-pick/revert and other --no-walk style commands only, would not be a regression for me. The multi-pick feature is still young, and I _suspect_ changing the meaning of A..B B..C for it would not inconvenience anybody.

I would even welcome a change in the meaning of B ^A: the most intuitive thing for it to do would be to cherry-pick the single commit B when and only when it is not an ancestor of A.

Jonathan

On Thu, Jan 12, 2012 at 02:11:22PM -0600, Jonathan Nieder wrote:

That's gross. :)

But thank you for providing a real-world example. I had a vague notion that the full power of the revision parser was not actually useful to people, but clearly not.

OTOH, if cherry-pick were more simplistic, you could perhaps get by with:

  list-revs-to-skip |
  xargs git rev-list --cherry-pick --right-only HEAD...topic --not |
  git cherry-pick --stdin

-Peff

Ramkumar Ramachandra <artagnon@gmail.com> writes:

Not really.

A rough approximation would be that if you see any negative ones (either coming from A..B or ^A), you would always want to walk, giving everything to prepare_revision_walk()-and-then-get_revision() machiery.

Otherwise you have only zero [*1*] or more positive ones, and you pick them in the order you find in the pending list, without bothering the revision traversal machinery at all [*2*].

So the answer is aboslutely no. "maint ^master" is the same as saying "master..maint".

[Footnote]

*1* You would probably want to error out if you got zero positive ones in this case (i.e. absolutely nothing was given, neither positive nor negative).

*2* The reason this is "rough" approximation is because we would probably want to do Jonathan's "maint..master master..next" someday, and when that happens, we would need to do much more than "do we have any negative? then send it through to prepare_revision_walk()". But we are not there yet, so I think the above is actually more or less the complete implementation.

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:

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:

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

Jeff King wrote:

Yes, exactly.  Another question: what should

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

do?

Jonathan Nieder <jrnieder@gmail.com> writes:

Revision ranges are not defined as a union of sets, but a single set as a range between zero or more bottom (UNINTERESTING) commits and zero or more top commits, the ones reachable from the top but not from the bottom, so the above will work as if you said "^master ^maint master next", which is the same as "master..next" (if you assume all of "maint" is contained in "master" all of which is contained in "next", of course).

And it is not likely to change soon.

In the longer term (or in an alternate universe where we were inventing Git from scratch today without any existing users), we may want to revamp the revision machinery, taking advantage of the recent addition of the "cmdline" facility to it, so that we would walk ranges "master..next" and "maint..master" independently, clearing the object flags as needed between the separate traversals as needed, and then take a union of these ranges, before returning results from get_revision() calls.