Re: [PATCH/RFC 2/2] Make path-limiting be incremental when possible.

On Thu, 30 Mar 2006, Junio C Hamano wrote:

Linus Torvalds [off-list ref] writes:

quoted

The reason I put "RFC" in the subject line is that while I've validated it 
various ways, like doing

	git-rev-list HEAD -- drivers/char/ | md5sum 

before-and-after on the kernel archive, it's "git-rev-list" after all. In 
other words, it's that really really subtle and complex central piece of 
software. So while I think this is important and should go in asap, I also 
think it should get lots of testing and eyeballs looking at the code.

Let me make sure I understand what is going on.

Currently, limit_list(), which is called when revs->limited is
set, serves two different purposes:

 * traverse the ancestry chain and mark ancestors of
   uninteresting commits also uninteresting;

Right.

We _also_ traverse the ancestry chain in the "walking" stage later in 
get_revision(), but if we have a "limit" case, we'll pre-traverse 
everything early in limit_list.

 * "simplify" each commit that is still interesting, by
   comparing the tree object of it and its parents.

Through "add_parent_to_list()", yes. 

We used to call limit_list() when we are limiting the commits by
paths, because that was what the latter does as a side effect of
add_parents_to_list().  You made it streamable by moving the
call to get_revision() and not calling limit_list() when you do
not have other reasons to call it.

Yes, and by using "add_parent_to_list()" instead of the 
non-pathname-limit-aware "pop_most_recent_commit()".

So we don't call limit-list any more, because we do the same thing in 
get_revision() that it used to do at limit time.

You currently do not do this streaming optimization when you
have to show simplified parents, because the streaming version
traverses ancestry chain one step at a time as it goes, and you
cannot obviously see who the final "fake" parent is until you
simplify the parents enouogh.

Yes. For exactly the same reason some other things ause us to do 
limit_list(): some ops simply need the fully connected end result in order 
to be able to work correctly.

 * get_commit_reference() sets "limited" when the user gives ^exclude
   commit.  no question about this --- we would need to see the
   reachability in this case.

Right.

 * when we are going to sort the result we are going to show,
   we set "limited" -- we cannot sort without knowing the set we
   are sorting.

Right.

 * giving commit timestamp limits via --max-age, --min-age
   etc. sets "limited".  I have doubts about this.

I agree. I looked at it when I did the "rev-list.c" vs "revision.c" split, 
but I wanted to do as few changes as possible, and for some reason we've 
always considered "time" to cause us to limit things.

However, I think your patch is wrong. Even if you don't limit things when 
we have a date specifier, you still want to stop doing traversal in 
limit_list when you hit that date. Why? Because it might be limited for 
some _other_ reason, eg due to --topo-order or or some other issue.

 * As to handling of --unpacked, exactly the same comment as
   "max-age" applies, but it might be even worse.  Marking an
   unpacked one "uninteresting" means if a packed commit refers
   to loose commit, the loose one will be also marked
   uninteresting, I think.

"--objects --unpacked" is an idiom to repack objects that are
still loose, but I suspect it would do interesting thing if the
commit is in a pack but its trees and blobs are still loose.  Am
I confused, or have I just spotted a potential (but hard to
trigger) bug?

Regardless of where you do the "unpacked" test, it will always really end 
up stopping when it hits a packed commit. So you won't ever get away from 
that.

So same logic applies. Once you hit a packed commit, you should stop, both 
in limit_list _and_ in get_revision(). Otherwise you'll do too much work 
when trying to limit things, for no gain.

The fact is, "--unpacked" means that we traverse the part of the chain 
that hasn't been packed yet. Anything that is packed automatically cuts 
off parsing, whether there is anything else unpacked below it or not. It's 
not a bug, it's a feature, and if you want to pack everything, you should 
just do

	git repack -a -d

and not use --unpacked.

Same goes for dates, btw. We've always stopped when we reached a certain 
date, even though there _could_ be commits before it that are from a more 
recent date (due to clocks being set wrong). Neither --unpacked nor 
--since=xyzzy are meant to be any kind of "guarantees" that you get all 
commits that match some pattern. They are just "stop early" rules.

		Linus

So the following is wrong:

..but the later part of the patch looks fine (modulo testing, of course):