threads / discuss / 39391

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

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

## tl;dr

5 messages between May 21, 2015 and May 22, 2015.

replies: 4people: 2as markdown or json

Mike Hommey· May 21, 2015, 06:15 UTC · lore

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

Junio C Hamano· May 21, 2015, 16:41 UTC · re: Mike Hommey · lore

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

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

Mike Hommey· May 21, 2015, 22:49 UTC · re: Junio C Hamano · lore

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

On Thu, May 21, 2015 at 09:41:55AM -0700, Junio C Hamano wrote:

Show 7 quoted lines

> 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

Junio C Hamano· May 21, 2015, 22:59 UTC · re: Mike Hommey · lore

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

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:

Show 20 quoted lines

> 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

Mike Hommey· May 22, 2015, 00:57 UTC · re: Junio C Hamano · lore

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

On Thu, May 21, 2015 at 03:59:48PM -0700, Junio C Hamano wrote:

Show 6 quoted lines

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

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