Revision walking, commit dates, slop

[Mike Hommey <mh@glandium.org>]

Hi,

There are established corner cases, where in a repo where commit dates
are not monotonically increasing, revision walking can go horribly
wrong. This was discussed in the past in e.g.
https://public-inbox.org/git/20150521061553.GA29269@glandium.org/

The only (simple) workable way, given the current algorithm, to get an
accurate view off rev-list is to essentially make slop infinite. This
works fine, at the expense of runtime.

Now, ignoring any modification for the above, I'm hitting another corner
case in some other "weird" history, where I have 500k commits all with
the same date. With such a commit dag, something as trivial as
`git rev-list HEAD~..HEAD` goes through all commits from the root commit
to HEAD, which takes multiple seconds, when the (obvious) output is one
commit.

It looks like the only way revision walking stops going through all the
ancestry is through slop, and slop is essentially made infinite by the
fact all commits have the same date (because of the date check in
still_interesting(). By extension, this means the workaound for the
first corner case above, which is to make slop infinite, essentially
makes all rev walking go through the entire ancestry of the commits
given on the command line.

It feels like some cases of everybody_uninteresting should shorcut slop
entirely, but considering the only way for slop to decrease at all is
when everybody_uninteresting returns true, that would seem like a wrong
assumption. But I'm also not sure what slop helps with in the first
place (but I don't have a clear view of the broader picture of how the
entire revision walking works).

Anyways, a rather easy way to witness this happening is to create a
dummy repo like:
  git init foo
  cd foo
  for i in $(seq 1 50); do
    echo $i > a;
    git add a;
    git commit -a -m $i;
  done

The something as simple as `git rev-list HEAD~..HEAD` will go through
all 50 commits (assuming the script above created commits in the same
second, which it did on my machine)

By the time both HEAD~ and HEAD have been processed, the revision
walking should have enough information to determine that it doesn't need
to go further, but still does. Even with something like HEAD~2..HEAD,
after the first round of processing parents it should be able to see
there's not going to be any more interesting commits.

I'm willing to dig into this, but if someone familiar with the
algorithm could give me some hints as to what I might be missing in the
big picture, that would be helpful.

Cheers,

Mike