Re: git-rev-list: proper lazy reachability

On 5/31/05, Linus Torvalds <torvalds@osdl.org> wrote:

Seems reasonable, though I think that in a graph like this:

    A 
  /  |  \ 
B  C  D
|  /   /
E
| \ 
F G

and searching for git-rev-list A ^B

it would actually be better to stop at E (printing A,B,C,D,E), rather than B because the contemporaneously parallel edits C and D and the common base E are relevant to evaluating B since they got merged with B into A from the common starting point E.

In the lingo of my epoch theory, this is searching to the next nearest epoch boundary past B.

My merge-order patch to rev-list which incorporates epoch theory is still on its way - it turned out that incrementally finding epoch boundaries was not quite as simple as I thought it would be. I expect I'll have a respectable looking patch available this weekend. The patch I have now works quite well for smaller graphs but fails on larger graphs because it relies on rational numbers with large numerators and denominators and these end up overflowing even 64 bit integers. I think I know how to fix it, but it will take me a few more days yet.

jon.