Re: [PATCH v4 1/2] revision.c: implement --reverse=before for walks

This topic has been rattling around in my head for a while, and I need to get it out now. :-)

First, a few notes:

 * I'm going to delete most of the context because I want to go back
to first principles here. Instead, I'll list what I think are the real
issues.

 * I have always had a suspicion that `--max-count` / `-n` was "done
wrong" in the first place, it's just that it's generally invisibly
wrong.

 * While all the revision-walking machinery normally shows commits
"newest first", there are several fundamental issues with defining
"newest" anyway. A lot of Git newcomers find this terribly confusing
-- usually a few weeks or months into use of Git, really.

It's important to note that the rev-walk machinery uses a priority queue, and that this is necessary because commits are in a directed graph, which cannot be presented linearly unless you're willing to: (a) add additional information (graph drawing, parent list, whatever), or (b) discard information. The `git log` and `git rev-list` documentation skimp a bit on this.

There is of course nothing wrong with discarding information when it's irrelevant. In fact, that's the whole point of abstraction, to toss out irrelevancies so that one can concentrate only on the relevant. And that's what all the limiting options for revision walking are for!

Sorting options affect the order in which items go into the priority queue. Limiting options affect which items go in, and sometimes, how many items come out. Display options affect what we see when the items come out, and this includes the sorting options since they come out in the order they're in there.

Thus, `--reverse` is a *display* option (part of sorting), while `--max-count` is a *limiting* option. It's just that, well, there's a special case when they're combined.

Junio noted:

And that's really the case here. Because `--max-count` was "done wrong" initially, we have a slight problem. Had it been done as a "window of items in the priority queue", we would always have gotten the limited-to-N items remaining in the queue after the selection process, displayed according to the display process. But when the display is going to be "in the order of items in the queue" and the limiting count is N items *and* the display doesn't reverse the queue, it suffices to display the first N items and then quit entirely. This is of course a nice space-and-time optimization.

As it turns out, the only display option that causes this optimization to be invalid is (or might be) `--reverse`.

Unfortunately, fixing the problem by simply defeating the "keep N items in the queue and only stop early (and maybe display as we go as well) if we're allowed" optimization -- the one that was applied prematurely, as it were -- will change the existing behavior of `git log -n 10 --reverse` in any repository with more than 10 commits in it. Had the over-optimization not been done, and someone wanted to add a "gather only N into the queue and then stop traversing, and then display" option, we could perhaps use `--stop-walk-(after|at)=n` as a new option.

As far as I can tell, the gripe that this exposes the priority queue mechanism is valid, but at best trivial, because knowing about the priority queue is crucial anyway. Beginners can skip it for a little while, but as soon as they find out that commits have two separate date stamps, and learn about `--date-order`, `--author-date-order`, and `--topo-order`, they need to learn about the queue.

If it's deemed acceptable to change the historic behavior of `--max-count` combined with `--reverse`, I'd suggest simply adding `--stop-walk-after` (perhaps with a slightly different name) to take over the historic behavior of `--max-count`, and make `--max-count` not over-optimize. If not, I'd suggest a new option, with a note in the documentation that `--max-count` has this odd behavior when combined with `--reverse`. Perhaps the new option could be called `--prio-queue-size=n`. The implementation can still optimize this (using the same code as before) when `--reverse` isn't in effect, since the effect is only visible with `--reverse`.

Chris