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

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

[Mike Hommey]

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

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

[Junio C Hamano]

Mike Hommey <mh@glandium.org> writes:

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

Yeah, that is well known (look for SLOP both in the code and list
archive).

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

[Mike Hommey]

On Thu, May 21, 2015 at 09:41:55AM -0700, Junio C Hamano wrote:
> Mike Hommey <mh@glandium.org> writes:
> 
> > My guess is that rev-walking is tripping on the fact that this repository
> > has commit dates in random order.
> 
> Yeah, that is well known (look for SLOP both in the code and list
> archive).

I found the recent thread about git describe --contains. (and now I
realize this is also why git describe --contains doesn't work quite well
for the same repository).

Now the question is what can we done in the short term? (short of
introducing something like generation numbers) I tried increasing
SLOP and to remove the date check (with the hope that making one or
both configurable might help). Neither fixed the particular test
case I started this thread with.

Mike

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

[Junio C Hamano]

Depends on why you are running rev-list.

If you want to know if one commit is contained in another, the way
that should work the most reliably is to use merge-base, as the
traversal engine of that command was written not to trust the commit
timestamps but go with the topology alone.

(pardon top-posting and overlong lines; typed in GMail)


On Thu, May 21, 2015 at 3:49 PM, Mike Hommey <mh@glandium.org> wrote:
> On Thu, May 21, 2015 at 09:41:55AM -0700, Junio C Hamano wrote:
>> Mike Hommey <mh@glandium.org> writes:
>>
>> > My guess is that rev-walking is tripping on the fact that this repository
>> > has commit dates in random order.
>>
>> Yeah, that is well known (look for SLOP both in the code and list
>> archive).
>
> I found the recent thread about git describe --contains. (and now I
> realize this is also why git describe --contains doesn't work quite well
> for the same repository).
>
> Now the question is what can we done in the short term? (short of
> introducing something like generation numbers) I tried increasing
> SLOP and to remove the date check (with the hope that making one or
> both configurable might help). Neither fixed the particular test
> case I started this thread with.
>
> Mike

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

[Mike Hommey]

On Thu, May 21, 2015 at 03:59:48PM -0700, Junio C Hamano wrote:
> Depends on why you are running rev-list.
> 
> If you want to know if one commit is contained in another, the way
> that should work the most reliably is to use merge-base, as the
> traversal engine of that command was written not to trust the commit
> timestamps but go with the topology alone.

So, specifically, rev-list was just a side use-case that happened to
show the same problem (or at least appeared to) when I was looking at
what the hell was happening. I should probably have started with my
actual failure instead, sorry for that. So here it is in the form of
a testcase:

$ 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
$ git rebase -i e90de3e5e045428e8f2b732882736dc93ce05f14 b

This lists plenty of commits instead of just a and b, like what would
happen if there weren't timestamps skews.

I've frequently used this kind of rebase in the past. It works most of
the time because the situation with timestamps is generally not a
problem. The reason I'm doing this kind of merge+rebase business is
that I have multiple topic branches that I need to rebase on top of each
other before pushing them upstream, and it's actually simpler, command-
wise, than actually rebasing the topics on top of each other.

Mike