Re: git-rev-list: proper lazy reachability

[Jon Seymour <jon.seymour@gmail.com>]

On 5/31/05, Linus Torvalds <torvalds@osdl.org> wrote:
> 
> Somebody should probably take a look at my simplistic algorithm, since it
> can probably be improved upon and/or fixed for corner-cases.

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.

-- 
homepage: http://www.zeta.org.au/~jon/
blog: http://orwelliantremors.blogspot.com/