git-rev-list: proper lazy reachability

Ok, I just made git-rev-list DTRT when you pass it a "beginning" and "end", ie it does proper reachability analysis _without_ parsing the whole set of commits.

It's probably buggy, so don't get too excited, but it seems to give the right results for something like

	git-rev-list v2.6.12-rc5 v2.6.12-rc4

which is basically "give me a rev-list of everything that is in rc5 but is not in rc4".

So now "git-rev-list a b" should be equivalent to "git-rev-tree a ^b", except it's faster, and it doesn't print out anything else.

Because it doesn't need to go all the way back to the root (only far enough back to be able to determine that there can be no more unreachable entries), it should be constant-time in the total history size. Doesn't matter if you've got a million revisions, if you asked for the difference between two "close" ones, it will be fast.

Somebody should probably take a look at my simplistic algorithm, since it can probably be improved upon and/or fixed for corner-cases.

		Linus

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.

On Tue, 31 May 2005, Jon Seymour wrote:

You're talking about something else - you worry about showing a graph, for example.

What git-rev-list A B does is literally for something like a "changelog" - what commits were added in A that weren't in B, and the list is A, C and D. Or, more commonly, used for something like

	git-rev-list HEAD v2.6.12-rc5 | git-diff-tree --stdin -v -p drivers/usb

which basically says "what changed since 2.6.12-rc5 in the drivers/usb tree"?

So in that situation, you really do _not_ want to see B and E, even if you'd need those two to make all the connections. Because you've seen B and E already (they were in v2.6.12-rc5), and if you're looking for a bug that didn't happen in that release, you really only want to see the new stuff.

		Linus

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

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

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.

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.

Linus Torvalds writes:

I have made gitk use git-rev-list instead of git-rev-tree, but it still absorbs the whole of git-rev-list's output before drawing anything. I'd like to make it draw the commit graph and list incrementally as it gets the output from git-rev-list, but to do that I need to know whether git-rev-list could ever print a commit ID *after* one of its parents. If it never does that then I can restructure the code to do the drawing incrementally fairly easily.

Paul.

On Tue, 31 May 2005, Paul Mackerras wrote:

You should never see a parent before a child from git-rev-list. I may have screwed something up when I move things between the two lists (the before/after thing needs to first do the reachability thing on one list, and then moves them to the "potential output list"), but I don't think so.

Anyway, at that point it would be a git-rev-list bug, so if you can make your code notice and complain ("git-rev-list listed parent before child") rather than silently show crud, that would help debugging it if it ever happened.

		Linus

On Tue, 31 May 2005, Linus Torvalds wrote:

Actually, I take that back.

A commit that has several children will see _a_ child before the parent is shown, but while the time-based ordering means that it _likely_ will order all children before the parent, now that I think about it, that's not guaranteed to be true. You could have

	      A
	     / \
	    B   |
	     \ /
	      C
	      |
	      D

and if C has a date that is before B, then git-rev-list would traverse the tree (and show it) in the order A C B.

In fact, even D might be listed before B is (eg, the person who committed B had a clock that was set to the last century, and so the date on that was wrong).

The thing is, since B has such an "old" date, the traversal assumes that it is old and very low down in the tree, and that it's better off parsing other commits first, so it will never look more closely at B and notice that it has a parent that has already been parsed.

So I guess you'll have to wait for the end and do the toposort after all. Sorry about the confusion on my part.

		Linus

Hi, Linus Torvalds wrote:

We could add a cache file, listing commit nodes which predate one of their parents. Hit one of those and you know you need to immediately examine their parents instead of waiting for them to come up in date order.

There shouldn't be too many of those in any tree.

Linus, what do you think rev-list should do given HEADs from two forks, like this?

    JC          git-rev-list JC LT ????
     |
     |  LT
     |   |
      \ /
       |
       |
       |

The above is often the shape of my working repository. I pull from you, commit a handful on top of your then-HEAD, and when I am about ready to submit, I pull from you again to find your HEAD advanced somewhat.

For patch-form submission, I need a list of my commits since I forked from you. Also I tend to rebase to your head often, instead of merging inside my working repository (which makes later e-mail patch-form submission more work for me), so even when I am not immediately submitting the changes I have in my fork, I need that list to forward port my changes.

JIT currently uses this to get this list (as a workaround):

    git-rev-list JC $(merge-base JC LT)

I am wondering if this "since they forked" is usually what the user wants. If that is the case then it would be great if I did not have to do the "merge-base" part outside.

Current "proper lazy reachability" version, btw, does something very unexpected for my use pattern. If you have more than one commits between the fork point and LT HEAD in the above picture, everything from the beginning of time to JC is given, or something silly like that.

Hello Junio, I pull the REMOTE_HEAD including objects but don't merge. After that I run:

system("git-rev-tree HEAD REMOTE_HEAD | sed -e 's/^[0-9]* //' | git-diff-tree --stdin -v ");

for bitkeeper I used the merge base approach (but at that time I only knew that this gives me any deltas in the current tree not in the remote tree, but didn't know how it worked).

bkparentdiff is aliased to `bk rset -hr`bk repogca`,+ | grep -v ^BitKeeper | bk gnupatch -du -e -h -T'

	Thomas

On Sat, 4 Jun 2005, Junio C Hamano wrote:

Ahh. Ok, I'll fix it. Indeed, I think it should give everything up to the merge base.

Yes. The whole thing is written to literally expect to see the "stop here" thing, and that's when it starts poisoning the well.

Does this fix it for you (untested, of course)?

		Linus
---

On Sat, 4 Jun 2005, Linus Torvalds wrote:

Btw, as shown by this patch, the lazy git-rev-list algorithm is actually _supposed_ to be able to handle a lot more complicated cases than what the command line interface allows.

In other words, maybe I should have used the same syntax as for git-rev-tree, because it _can_ handle things like "show me all revisions that are reachable from a or b, but are _not_ reachable from c or d or e.

Is that useful? I dunno. It might be useful for somebody like Jeff, who has lots of different heads, and he could say "ok, show me what is in all my network driver heads, but isn't in linus' tree".

Would people prefer to have "git-rev-list" take arguments like

	git-rev-list a b ^c ^d

the way git-rev-tree does?

		Linus

LT> On Sat, 4 Jun 2005, Linus Torvalds wrote:

Will check later.

LT> Would people prefer to have "git-rev-list" take arguments like LT> git-rev-list a b ^c ^d LT> the way git-rev-tree does?

I do not expect myself to maintain many heads like Jeff, I cannot comment on how well that "many heads" feature would work in practice, but I would vote "a ^b" syntax to match git-rev-tree.

Dear diary, on Sat, Jun 04, 2005 at 05:51:13PM CEST, I got a letter where Linus Torvalds <torvalds@osdl.org> told me that...

Yes, please. I think that usage is more consistent and more flexible.

LT> Yes. The whole thing is written to literally expect to see the "stop here" LT> thing, and that's when it starts poisoning the well.

LT> Does this fix it for you (untested, of course)?

Yes, it does.