Re: [RFH] revision limiting sometimes ignored

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Feb 6, 2008, 10:34 UTC
Message-ID: <alpine.LFD.1.00.0802060216510.2967@woody.linux-foundation.org>
In-Reply-To: <7vwspi4poh.fsf@gitster.siamese.dyndns.org>

On Tue, 5 Feb 2008, Junio C Hamano wrote:

> 
> I really wish this was still May 2005.  Then I (actually, you)
> could just decree:

Yeah, we really should have done that, when this came up last.

We could still decide it's a good idea to do, and simply decide that

 - within all-new ranges (that *do* have generation numbers) we can use 
   the generation number to give certain guarantees.

 - when any commits involved don't have generation numbers, we just fall 
   back on the not-strict-guarantees-use-commit-date-heuristics.

but here's something I whipped up because I woke up at 2AM and decided that there is a simple heuristic that works *most* of the time.. We just add a bit of slop, namely:

 - we always walk an extra SLOP commits from the source list even if we 
   decide that the source list is probably all done (unless the source is 
   entirely empty, of course, because then we really can't do anything at 
   all)

 - we keep track of the date of the last commit we added to the 
   destination list (this will *generally* be the oldest entry we've seen 
   so far)

 - we compare that with the youngest entry (the first one) of the source 
   list, and if the destination is older than the source, we know we want 
   to look at the source.

 - otherwise, do the "everybody_uninteresting()" test to see whether we're 
   still interested in the source.

I dunno. It's really late (or early ;), and I'm having a headache. Maybe it doesn't really work. But the idea is that this should be able to handle the few occasional incorrect timestamps. Maybe.

		Linus

---
 revision.c |   35 ++++++++++++++++++++++++++++++++++-
 1 files changed, 34 insertions(+), 1 deletions(-)

diff --git a/revision.c b/revision.c
index 6e85aaa..a50ae02 100644
--- a/revision.c
+++ b/revision.c
@@ -558,8 +558,39 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 	free_patch_ids(&ids);
 }
 
+/* How many extra uninteresting commits we want to see.. */
+#define SLOP 5
+
+static int still_interesting(struct commit_list *src, unsigned long date, int slop)
+{
+	/*
+	 * No source list at all? We're definitely done..
+	 */
+	if (!src)
+		return 0;
+
+	/*
+	 * Does the destination list contain entries with a date
+	 * before the source list? Definitely _not_ done.
+	 */
+	if (date < src->item->date)
+		return SLOP;
+
+	/*
+	 * Does the source list still have interesting commits in
+	 * it? Definitely not done..
+	 */
+	if (!everybody_uninteresting(src))
+		return SLOP;
+
+	/* Ok, we're closing in.. */
+	return slop-1;
+}
+
 static int limit_list(struct rev_info *revs)
 {
+	int slop = SLOP;
+	unsigned long date = ~0ul;
 	struct commit_list *list = revs->commits;
 	struct commit_list *newlist = NULL;
 	struct commit_list **p = &newlist;
@@ -579,12 +610,14 @@ static int limit_list(struct rev_info *revs)
 			return -1;
 		if (obj->flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
-			if (everybody_uninteresting(list))
+			slop = still_interesting(list, date, slop);
+			if (!slop)
 				break;
 			continue;
 		}
 		if (revs->min_age != -1 && (commit->date > revs->min_age))
 			continue;
+		date = commit->date;
 		p = &commit_list_insert(commit, p)->next;
 
 		show = show_early_output;