Re: [RFH] revision limiting sometimes ignored

[Linus Torvalds <torvalds@linux-foundation.org>]

On Sat, 2 Feb 2008, Jeff King wrote:
> 
> OK, there is definitely a bug here, but I'm having some trouble figuring
> out the correct fix. It's in the revision walker, so I have cc'd those
> who are more clueful than I.

Ok, I agree that there is a bug, and your two-liner fix is a "fix" in that 
it works, but I think it's absolutely the wrogn fix because it is totally 
unacceptable from a performance angle. We obviously need to break out of 
the loop before we have walked the whole commit chain.

>  		if (obj->flags & UNINTERESTING) {
>  			mark_parents_uninteresting(commit);
> -			if (everybody_uninteresting(list))
> -				break;
>  			continue;
>  		}

So I think the real problem here is not that the logic is wrong in 
general, but that there is one *special* case where the logic to break out 
is wrong.

And that special case is when we hit the root commit which isn't negative.

That case is special because *normally*, if we have a positive commit, we 
will always continue to walk the parents of that positive commit, so the 
"everybody_interesting()" check will not trigger. BUT! If we hit a root 
commit and it is positive, that won't happen (since, by definition, it has 
no parents to keep the list populated with), and now we break out early.

So I think your fix is wrong, but it's "close" to right: I suspect that we 
can fix it by marking the "we hit the root commit" case, and just 
disabling it for that case.

This patch is untested and obviously won't even compile (I didn't actually 
add the "hit_root" bitfield to the revision struct), but shows what I 
*think* should fix this issue, without the performance problem.

But maybe I haven't thought it entirely through, and there is some other 
case that can trigger this bug.

So please somebody double-check my thinking.

			Linus

---
diff --git a/revision.c b/revision.c
index 6e85aaa..0e90988 100644
--- a/revision.c
+++ b/revision.c
@@ -456,6 +456,9 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, str
 
 	left_flag = (commit->object.flags & SYMMETRIC_LEFT);
 
+	if (!commit->parents)
+		revs->hit_root = 1;
+
 	rest = !revs->first_parent_only;
 	for (parent = commit->parents, add = 1; parent; add = rest) {
 		struct commit *p = parent->item;
@@ -579,7 +582,7 @@ static int limit_list(struct rev_info *revs)
 			return -1;
 		if (obj->flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
-			if (everybody_uninteresting(list))
+			if (!revs->hit_root && everybody_uninteresting(list))
 				break;
 			continue;
 		}