Occasional wrong behavior of rev-walking (rev-list, log, etc.)

[Mike Hommey <mh@glandium.org>]

Hi,

I noticed that in some weird cases, git rev-list and friends would
appear to not do their work as intended. As I wasn't entirely sure at
the time I saw previous occurrence (which involved lots of refs and
big history) , I kept that on the side to look back later, but today,
it happened again on a somewhat smaller testcase, albeit, on a big
repository.

I was able to reproduce it with the following:

$ git clone https://github.com/mozilla/gecko-dev
$ cd gecko-dev
$ git checkout -b a 4d3f25020072867e19ad6d840a73c8d77ea040bd
$ git commit --allow-empty -m a
$ git checkout -b b e90de3e5e045428e8f2b732882736dc93ce05f14
$ git commit --allow-empty -m b
$ git merge a -m merge

Now here's the problem:

$ git rev-list e90de3e5e045428e8f2b732882736dc93ce05f14..b | wc -l
86

But:
$ git rev-list e90de3e5e045428e8f2b732882736dc93ce05f14 | grep 4d3f25020072867e19ad6d840a73c8d77ea040bd
4d3f25020072867e19ad6d840a73c8d77ea040bd

So 4d3f25020072867e19ad6d840a73c8d77ea040bd is in
e90de3e5e045428e8f2b732882736dc93ce05f14's history, which means the only
thing that's on top of e90de3e5e045428e8f2b732882736dc93ce05f14 in b is
the 3 commits created above.

My guess is that rev-walking is tripping on the fact that this repository
has commit dates in random order.

Mike