Re: git-rev-list: proper lazy reachability

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.

What happens is that it walks the tree "time-first" (not depth-first or 
breadth-first, but "most-recent-first"), which tends to approximate what 
we want, and when it sees "B" it will mark all of its children as 
uninteresting since they were clearly seen. So it will actually have 
gotten all the way to E before it can tell that it has seen enough.

The thing that makes git-rev-list preferred over git-rev-tree is that it 
can avoid looking at F and G and older parents, since it's clear by E that 
walking the tree any further would be pointless, and all the commits we 
could look at are already marked uninteresting.

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.

(Well, slightly more too: you'd have to add the uninteresting commits to
the list, and mark the end object itself as being ignored, but that's two
more trivial lines. Right now the code knows that it won't even add some 
objects to the output list, so..).

		Linus
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html