From 155808178ee80aaadfeb3d982d931e5b2e3ed307 Mon Sep 17 00:00:00 2001
From: "Shawn O. Pearce" <spearce@spearce.org>
Date: Tue, 25 Mar 2008 03:28:50 -0400
Subject: [PATCH] Carry uninteresting flags back through already processed
 parents

If an interesting branch has had a chance to visit through the
parent commits that are behind the merge base of the interesting
branch and the uninteresting branch we won't get UNINTERESTING
carried into those commits, but they have already been produced
as output from the pending generator.

We carry the flags back through the parents for any branch we have
already SEEN (pushed into the pending queue), thus making sure the
UNINTERESTING flag goes back as far as we can get with our current
parsed parent lists.  Since single commit chains are very common
(the so called strand-of-pearls) we try to perform a tail recursion
on the first parent and only use stack recusion when we need to
walk down the other side branches of a merge.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/revwalk/AbstractPendingGenerator.java     | 38 +++++++++++++++++++---
 1 file changed, 34 insertions(+), 4 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractPendingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractPendingGenerator.java
index c6fd6f0d..20f96329 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractPendingGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractPendingGenerator.java
@@ -34,6 +34,10 @@ import org.spearce.jgit.revwalk.filter.RevFilter;
  * of the commits and return them to the caller.
  */
 abstract class AbstractPendingGenerator extends Generator {
+	private static final int PARSED = RevWalk.PARSED;
+
+	private static final int SEEN = RevWalk.SEEN;
+
 	protected final RevWalk walker;
 
 	private final AbstractRevQueue pending;
@@ -75,12 +79,16 @@ abstract class AbstractPendingGenerator extends Generator {
 
 				final int carry = c.flags & RevWalk.CARRY_MASK;
 				for (final RevCommit p : c.parents) {
-					p.flags |= carry;
-					if ((p.flags & RevWalk.SEEN) != 0)
+					if ((p.flags & SEEN) != 0) {
+						if (carry != 0)
+							carryFlags(p, carry);
 						continue;
-					if ((p.flags & RevWalk.PARSED) == 0)
+					}
+					if ((p.flags & PARSED) == 0)
 						p.parse(walker);
-					p.flags |= RevWalk.SEEN;
+					p.flags |= SEEN;
+					if (carry != 0)
+						carryFlags(p, carry);
 					pending.add(p);
 				}
 
@@ -103,6 +111,28 @@ abstract class AbstractPendingGenerator extends Generator {
 		}
 	}
 
+	private static void carryFlags(RevCommit c, final int carry) {
+		// If we have seen the commit it is either about to enter our
+		// pending queue (first invocation) or one of its parents was
+		// possibly already visited by another path _before_ we came
+		// in through this path (topological order violated). We must
+		// still carry the flags through to the parents.
+		//
+		for (;;) {
+			c.flags |= carry;
+			if ((c.flags & SEEN) == 0)
+				return;
+			final RevCommit[] pList = c.parents;
+			final int n = pList.length;
+			if (n == 0)
+				return;
+
+			for (int i = 1; i < n; i++)
+				carryFlags(pList[i], carry);
+			c = pList[0];
+		}
+	}
+
 	/**
 	 * Determine if a commit should produce in the output.
 	 * 
-- 
2.11.4.GIT