Re: Change set based shallow clone

[linux@horizon.com]

> Anyhow the basic is:
> 
> -git-rev-list starts outputting the data early (order is not guaranteed)
> 
> -before to mark for output a revision check if it breaks --topo-order
> 
> -if the above is true store the revision away and *do not send*
> 
> - at the end you get an early started steram of topological corrects
> revisions without
> preordering, just because you filter away the (few?) revisions that
> are not in order.
> The list you get is guaranteed to be in topo order although my not be complete.
> 
> - _then_  you send the missing revisions that where previously
> filtered out. At this stage the receiver has already drwan the graph,
> indeed it has start drwaing as soon as the first revisons arrived and
> *very important* receiver used old and fast topo-order parsing code.
> 
> - finally the fixup routine at receiver's end updates the graph with
> the info from the small set of out of order revisions filtered out
> before and sent at the end (only this small set is sent at the end).

The problem is that the gitk display code doesn't *like* input like this;
it's only designed to append to a list.  Handling insertions would be
hard work for a rare corner case, and a perpetual source of bugs.

Unless gitk does a complete second pass, or course, which would
guarantee an annoying flicker a few seconds after startup.
And Twice the work.

The original alternative was to note that out-of-order commits
usually aren't *very* out of order.  So if gitk could checkpoint
the state of its display algorithm periodically, it could just, when
seeing an out-of-order commit, rewind to the last checkpoint
before the problem and replay while merging in the corrections.

While that is potentially O(n^2) (if you feed it all the commits
in reverse order), in practice it
- Is less than 2*n work, and
- Always maintains the longest possible correct prefix of
  recent commits.  It's the old stuff that takes a while to
  fill in.

Either way, gitk has to have topo-sorting code added to it.  I think
Linus' idea was to avoid that.