[BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Kevin Ballard]

-----------------------------------------------------------------------------
Running the command `git rev-list --no-walk A B C` should be expected to emit
the commits in the same order as they were specified. This is especially
important as the same machinery is used for `git cherry-pick`, and so saying
`git cherry-pick A B C` can be expected to pick A before B, and B before C.

This does not happen.

Instead, it appears to be sorting the given commits according to the commit
timestamp. To make matters worse, it's not a stable sort. If commits A and
B have the same timestamp (for example, if they were rebased together), then
git cherry-pick tends to apply B before A.

Is there any rationale for this behavior? Any place where it makes sense to
reorder the commits in this fashion? As far as I'm concerned, typing
`git cherry-pick A B C` should behave identically to typing

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

regardless of the actual commit dates on A, B, and C.

-Kevin Ballard

Re: [BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Junio C Hamano]

Kevin Ballard <kevin@sb.org> writes:

> Is there any rationale for this behavior?

Not a rationale, but an explanation is that most of the time we walk the
history and sorting by date is the first thing that needs to be done, and
the --no-walk option was an afterthought that was tucked in.

I suspect that a three-liner patch to revision.c:prepare_revision_walk()
would give you what you want.  Instead of calling insert-by-date, you
append to the tail when revs->no_walk is given, or something.

Re: [BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Kevin Ballard]

On Jan 7, 2011, at 5:00 PM, Junio C Hamano wrote:

> Kevin Ballard <kevin@sb.org> writes:
> 
>> Is there any rationale for this behavior?
> 
> Not a rationale, but an explanation is that most of the time we walk the
> history and sorting by date is the first thing that needs to be done, and
> the --no-walk option was an afterthought that was tucked in.
> 
> I suspect that a three-liner patch to revision.c:prepare_revision_walk()
> would give you what you want.  Instead of calling insert-by-date, you
> append to the tail when revs->no_walk is given, or something.

It almost works, but not quite. My inclination is to say
`git rev-list --no-walk A B C` should emit A B C in that order. Implemented
this way, `git rev-list --no-walk ^HEAD~3 HEAD` emits commits in the wrong
order, and I can't figure out how to change that. If I implement
`git rev-list --no-walk A B C` to emit C B A instead, then the test for
`git cherry-pick --stdin` fails (t3508), and I don't know why.

-Kevin Ballard

Re: [BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Junio C Hamano]

Kevin Ballard <kevin@sb.org> writes:

> It almost works, but not quite. My inclination is to say
> `git rev-list --no-walk A B C` should emit A B C in that order. Implemented
> this way, `git rev-list --no-walk ^HEAD~3 HEAD` emits commits in the wrong
> order,

"git rev-list --no-walk ^HEAD~3 HEAD"?  Isn't it a nonsense?  If it is "no
walk", then why do you even list a negative one?


As to cherry-pick, I wouldn't be surprised if it relies on the current
internal working of pushing commits in the date order to the queue
regardless of how they were given from the command line.

Indeed, it does exactly that, and then tries to compensate it---notice
that builtin/revert.c:prepare_revs() gives "revs->reverse" to it.  That
also needs to be fixed.

Re: [BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Kevin Ballard]

On Jan 7, 2011, at 9:41 PM, Junio C Hamano wrote:

> Kevin Ballard <kevin@sb.org> writes:
> 
>> It almost works, but not quite. My inclination is to say
>> `git rev-list --no-walk A B C` should emit A B C in that order. Implemented
>> this way, `git rev-list --no-walk ^HEAD~3 HEAD` emits commits in the wrong
>> order,
> 
> "git rev-list --no-walk ^HEAD~3 HEAD"?  Isn't it a nonsense?  If it is "no
> walk", then why do you even list a negative one?

That seemed odd to me too, but t3508 tests to make sure git cherry-pick accepts
that syntax. Specifically it tests `git cherry-pick ^first fourth`. It does
make a certain sense, though; it should be (and, I believe, is) equivalent to
saying `git rev-list --no-walk HEAD~3..HEAD`, though I don't know if it's
handled the same internally.

> As to cherry-pick, I wouldn't be surprised if it relies on the current
> internal working of pushing commits in the date order to the queue
> regardless of how they were given from the command line.

My belief is that it doesn't. It sets the reverse flag, so it gets the oldest
commit first. I think it's always just been tested taking commits in the same
order that they were committed, which seems fine except when two commits have
the same date. In that case, if A and B have the same date, then A B C will
get transformed to B A C. It's possible that this one quirk can be fixed by
changing the date test in commit_list_insert_by_date to use <= instead of <,
but that still leaves the issue where `git cherry-pick A B C` will sort those
commits even if the user explicitly wanted to apply them in the given order.

I suspect this just wasn't noticed before because cherry-pick didn't used to
accept multiple commits, and after that support was added, nobody's tried to
cherry-pick commits in a different order than they were committed.

> Indeed, it does exactly that, and then tries to compensate it---notice
> that builtin/revert.c:prepare_revs() gives "revs->reverse" to it.  That
> also needs to be fixed.

I did see that, I just left it out of my explanation.

-Kevin Ballard

Re: [BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> "git rev-list --no-walk ^HEAD~3 HEAD"?  Isn't it a nonsense?  If it is "no
> walk", then why do you even list a negative one?

The above was my thinko.

When you explicitly give range to no-walk, you override that no-walk with
"please walk".  This is primarily to help Linus who wanted to do "git show
HEAD~3..HEAD"---see how his thinking changed over time by comparing
aa27e461 and f222abde.

The right fix then would be to first always add in the order things were
given, and sort by date at the end after adding everything to queue and we
still have no_walk set, or something like that.

Re: [BUG] git rev-list --no-walk A B C sorts by commit date incorrectly

[Martin von Zweigbergk]

On Sat, 8 Jan 2011, Junio C Hamano wrote:

> Junio C Hamano <gitster@pobox.com> writes:
> 
> > "git rev-list --no-walk ^HEAD~3 HEAD"?  Isn't it a nonsense?  If it is "no
> > walk", then why do you even list a negative one?
> 
> The above was my thinko.
> 
> When you explicitly give range to no-walk, you override that no-walk with
> "please walk".  This is primarily to help Linus who wanted to do "git show
> HEAD~3..HEAD"---see how his thinking changed over time by comparing
> aa27e461 and f222abde.

Just a quick note: I didn't know that 'git show' was supposed to
support that syntax, so I had try it out. When I ran 'git show
origin/master..' on my branch, which was not rebase on top of
origin/master, it seemed to print the history all the way back. It
seems to stop only if all the positive refences contain the negative
reference. Is this intended? Not that it matter much, since 'git log
-p' seems to do the same thing but stops where I expect...