Re: git-rev-list: proper lazy reachability

From: Jon Seymour <jon.seymour@gmail.com>
Date: Jun 1, 2005, 00:14 UTC
Message-ID: <2cfc4032050531171437d5d9eb@mail.gmail.com>
In-Reply-To: <Pine.LNX.4.58.0505310758270.1876@ppc970.osdl.org>

On 6/1/05, Linus Torvalds <torvalds@osdl.org> wrote:

Show 19 quoted lines

> 
> 
> On Tue, 31 May 2005, Jon Seymour wrote:
> >
> >      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)
> 
> Btw, you probably looked at the actual code, so you know this, but maybe
> it wasn't clear to everybody else: the code obviously _will_ look at all
> of ABCDE before it can even decide that it should print out ACD, since it
> really needs to.

I did look at the code and concluded that ACD would be displayed and simply assumed B would also be displayed. Anyway, you are right, for the purposes you are interested in neither B nor E are interesting.

Show 8 quoted lines

> 
> But if somebody wanted to actually show this as a _graph_, what you would
> probably want is actually all of ABCDE, except you'd get the "interesting"
> bit separately (ie ACD would be tagged some way). Then you could show a
> sane graph that is colored by whether something is new or not, for
> example. That's absolutely trivial to do wiyth the new rev-list algorithm,
> in case somebody really cares - it's literally just changing the printout
> to show the entries marked "ignored" with some extra marking.

This will also fall pretty naturally out of the --merge-order patch that I am working on with an appropiate tweak. But I'll shut up about that until I have code to share...

jon.