Re: git-rev-list: proper lazy reachability

On Tue, 31 May 2005, Jon Seymour wrote:

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