Re: [RFH] revision limiting sometimes ignored

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Feb 4, 2008, 17:32 UTC
Message-ID: <alpine.LFD.1.00.0802040922480.3034@hp.linux-foundation.org>
In-Reply-To: <20080203043310.GA5984@coredump.intra.peff.net>

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.

Show 6 quoted lines

>  		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;
 		}