Re: [RFH] revision limiting sometimes ignored

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Feb 4, 2008, 20:03 UTC
Message-ID: <alpine.LFD.1.00.0802041146060.3034@hp.linux-foundation.org>
In-Reply-To: <7vr6fsk08w.fsf@gitster.siamese.dyndns.org>

On Mon, 4 Feb 2008, Junio C Hamano wrote:

> 
> However, I am afraid that is not quite enough.  It is not just
> "when we hit the root".

You're right. The proper test is actually "is the list of commits disconnected".

Which is not an entirely trivial thing to test for efficiently.

I suspect that we can solve it by not even bothering to be efficient, and instead just ask that question when we hit the "are all commits negative" query.

Gaah. This is that stupid apporach. The smarter one might be harder, especially for the special cases where you truly have two totally unconnected trees, ie:

	a -> b -> c

	d -> e -> f

and do

	git rev-list c f ^b ^e

were you actually do not _have_ a single connected graph at all, but you know the result should be "c" and "f" because they are *individually* connected to what we already know is uninteresting.

Not really tested at all, not really thought through. And that recursion avoidance could be smarter.

			Linus

---
 revision.c |   37 ++++++++++++++++++++++++++++++++++++-
 1 files changed, 36 insertions(+), 1 deletions(-)

diff --git a/revision.c b/revision.c
index 6e85aaa..26b2343 100644
--- a/revision.c
+++ b/revision.c
@@ -558,6 +558,41 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 	free_patch_ids(&ids);
 }
 
+static inline int commit_is_connected(struct commit *commit)
+{
+	struct commit_list *parents;
+	for (;;) {
+		if (commit->object.flags & UNINTERESTING)
+			return 1;
+		parents = commit->parents;
+		if (!parents)
+			return 0;
+		if (parents->next)
+			break;
+		commit = parents->item;
+	}
+
+	do {
+		if (!commit_is_connected(parents->item))
+			return 0;
+		parents = parents->next;
+	} while (parents);
+	return 1;
+}
+
+/* Check that the positive list is connected to the negative one.. */
+static int is_connected(struct commit_list *list)
+{
+	while (list) {
+		struct commit *commit = list->item;
+
+		list = list->next;
+		if (!commit_is_connected(commit))
+			return 0;
+	}
+	return 1;
+}
+
 static int limit_list(struct rev_info *revs)
 {
 	struct commit_list *list = revs->commits;
@@ -579,7 +614,7 @@ static int limit_list(struct rev_info *revs)
 			return -1;
 		if (obj->flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
-			if (everybody_uninteresting(list))
+			if (everybody_uninteresting(list) && is_connected(newlist))
 				break;
 			continue;
 		}