Re: Unresolved issues

On Mon, 17 Mar 2008, Junio C Hamano wrote:

* revision.c::limit_list() breakage
  $gmane/72324
  t/t6009

  When you run "git rev-list A..B C", and there is a commit in the chain
  between A and B whose timestamp is much older than its parent, sometimes
  we fail to mark C as reachable from A (hence not interesting) even when
  it actualy is.  This is very expensive to solve in general, and we are
  not going to introduce "generation number" field to the commit objects,
  so we may have to settle with a heuristic.

Here is the already posted heuristic that fixes both t/t6009 and the 
real-world case that triggered the whole discussion.

It's certainly not perfect, but I think it's likely an improvement on what 
we have now, and it should be robust in the face of the _occasional_ wrong 
date.

Now, if there are consistently totally bogus dates, the SLOP thing won't 
help, but ...

		Linus
---
From: Linus Torvalds <torvalds@woody.linux-foundation.org>

Make revision limiting more robust against occasional bad commit dates

The revision limiter uses the commit date to decide when it has seen
enough commits to finalize the revision list, but that can get confused
if there are incorrect dates far in the past on some commits.

This makes the logic a bit more robust by

 - 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.

which causes occasional date mishaps to be handled cleanly.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 revision.c |   46 +++++++++++++++++++++++++++++++++++++---------
 1 files changed, 37 insertions(+), 9 deletions(-)

diff --git a/revision.c b/revision.c
index 63bf2c5..196fedc 100644
--- a/revision.c
+++ b/revision.c

@@ -564,14 +564,39 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 	free_patch_ids(&ids);
 }
 
-static void add_to_list(struct commit_list **p, struct commit *commit, struct commit_list *n)
+/* 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)
 {
-	p = &commit_list_insert(commit, p)->next;
-	*p = n;
+	/*
+	 * 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;

@@ -591,16 +616,19 @@ static int limit_list(struct rev_info *revs)
 			return -1;
 		if (obj->flags & UNINTERESTING) {
 			mark_parents_uninteresting(commit);
-			if (everybody_uninteresting(list)) {
-				if (revs->show_all)
-					add_to_list(p, commit, list);
-				break;
-			}
-			if (!revs->show_all)
-				continue;
+			if (revs->show_all)
+				p = &commit_list_insert(commit, p)->next;
+			slop = still_interesting(list, date, slop);
+			if (slop)
+				continue;
+			/* If showing all, add the whole pending list to the end */
+			if (revs->show_all)
+				*p = list;
+			break;
 		}
 		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;