Re: [PATCH v2] rev-list docs: clarify --topo-order description

From: Thomas Rast <trast@student.ethz.ch>
Date: Aug 17, 2012, 17:37 UTC
Message-ID: <87obm9a07z.fsf@thomas.inf.ethz.ch>
In-Reply-To: <7v1uj5wi72.fsf@alter.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

Show 23 quoted lines

> Thomas Rast <trast@inf.ethz.ch> writes:
>
>> However, suppose we knew generation numbers.  I haven't actually looked
>> into the old threads again, but my understanding was that they are
>> numbers g(C) attached to each commit C such that
>>
>>   g(C) = 1 + max(g(P) for P a parent of C)   for non-root commits
>>
>>   g(C) = 0                                   for root commits
>>
>> They are invariant given the commit, so they can be cached.
>> ...
>> I hope I got that right.  The order of commits is still entirely
>> determined by the choice of "any tentative source", but the algorithm
>> should now stream nicely once the generation numbers are known.
>
> That matches the definition of generation number I remember from the
> old discussion.  Now look at the illustration in this discussion
> again:
>
>       ---A---B---C---D
>                       \
>     ---1---2---3---4---* = HEAD

[...]

Show 13 quoted lines

> The numbered commits 1 2 3 4 are building on top of recent "master",
> while alphabetized A B C D are building on aged maintenance track.
> The difference in generation numbers between 1 and 2, 2 and 3,... A
> and B, B and C, C and D are all one, and HEAD (the tip of 'pu') would
> have generation number of commit 4 plus 1, as commit 4's generation
> number would be a thousand or more ahead of that of commit D.  And
> there are a thousand ancestors of '1' with larger generation numbers
> than 'D'.
>
> When the user runs "git log" (i.e. the casual "the last few commit"
> macthes), the expectation of the user is "I want to see what I did
> recently".  If you substituted the commit timestamp with such a
> generation number, how would that expectation satisified?

Umm, have you looked at the algorithm I proposed?

It does not substitute the generation numbers for anything, let alone the date. It merely uses them to determine a point where it knows "enough" of the history to be able to emit the next commit; that is, where it can use the generation numbers to prove that no unknown commit can be a descendant of what it wants to emit next.

It does *not* have to use the generation numbers in the final ordering of the commits. That final order is determined by how the algorithm chooses the next candidate commit. If you use a stack, it winds up being --topo-order. If you use a date-ordered priority queue, it becomes --date-order.

So really, this is only about modifying the algorithm that generates the existing order to allow for streaming output as it reads through history.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch