Merge changes Ia95da478,I2773aa94,Ib745645f,I92c65f34,Ibb714002, ...

* changes:
  Remove BitmapRevFilter.getCountOfLoadedCommits
  Make BitmapBuilder.getBitmapIndex public
  Deprecate BitmapBuilder.add and introduce simpler addObject method
  Add @Override annotations to BitmapIndexImpl
  Rely on bitmap RevFilter to filter walk during bitmap selection
  Use 'reused' bitmap to filter walk during bitmap selection
  Rely on bitmap RevFilter to filter tip commit setup walk
  Use 'reused' bitmap to filter tip commit setup walk
  Include ancestors of reused bitmap commits in reuse bitmap again

4 files changed, 124 insertions, 25 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BitmapIndexImpl.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BitmapIndexImpl.java
index 5786019e9f..47adb914f0 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BitmapIndexImpl.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/BitmapIndexImpl.java
@@ -85,6 +85,7 @@ public class BitmapIndexImpl implements BitmapIndex {
 		return packIndex;
 	}
 
+	@Override
 	public CompressedBitmap getBitmap(AnyObjectId objectId) {
 		EWAHCompressedBitmap compressed = packIndex.getBitmap(objectId);
 		if (compressed == null)
@@ -92,6 +93,18 @@ public class BitmapIndexImpl implements BitmapIndex {
 		return new CompressedBitmap(compressed);
 	}
 
+	public CompressedBitmap toBitmap(PackBitmapIndex i,
+			EWAHCompressedBitmap b) {
+		if (i != packIndex) {
+			throw new IllegalArgumentException();
+		}
+		if (b == null) {
+			return null;
+		}
+		return new CompressedBitmap(b);
+	}
+
+	@Override
 	public CompressedBitmapBuilder newBitmapBuilder() {
 		return new CompressedBitmapBuilder();
 	}
@@ -106,10 +119,10 @@ public class BitmapIndexImpl implements BitmapIndex {
 		return position;
 	}
 
-	int addObject(AnyObjectId objectId, int type) {
+	int findOrInsert(AnyObjectId objectId, int type) {
 		int position = findPosition(objectId);
 		if (position < 0) {
-			position = mutableIndex.addObject(objectId, type);
+			position = mutableIndex.findOrInsert(objectId, type);
 			position += indexObjectCount;
 		}
 		return position;
@@ -200,8 +213,9 @@ public class BitmapIndexImpl implements BitmapIndex {
 	private final class CompressedBitmapBuilder implements BitmapBuilder {
 		private ComboBitset bitset = new ComboBitset();
 
+		@Override
 		public boolean add(AnyObjectId objectId, int type) {
-			int position = addObject(objectId, type);
+			int position = findOrInsert(objectId, type);
 			if (bitset.contains(position))
 				return false;
 
@@ -215,17 +229,26 @@ public class BitmapIndexImpl implements BitmapIndex {
 			return true;
 		}
 
+		@Override
 		public boolean contains(AnyObjectId objectId) {
 			int position = findPosition(objectId);
 			return 0 <= position && bitset.contains(position);
 		}
 
+		@Override
+		public BitmapBuilder addObject(AnyObjectId objectId, int type) {
+			bitset.set(findOrInsert(objectId, type));
+			return this;
+		}
+
+		@Override
 		public void remove(AnyObjectId objectId) {
 			int position = findPosition(objectId);
 			if (0 <= position)
 				bitset.remove(position);
 		}
 
+		@Override
 		public CompressedBitmapBuilder or(Bitmap other) {
 			if (isSameCompressedBitmap(other)) {
 				bitset.or(((CompressedBitmap) other).bitmap);
@@ -238,6 +261,7 @@ public class BitmapIndexImpl implements BitmapIndex {
 			return this;
 		}
 
+		@Override
 		public CompressedBitmapBuilder andNot(Bitmap other) {
 			if (isSameCompressedBitmap(other)) {
 				bitset.andNot(((CompressedBitmap) other).bitmap);
@@ -250,6 +274,7 @@ public class BitmapIndexImpl implements BitmapIndex {
 			return this;
 		}
 
+		@Override
 		public CompressedBitmapBuilder xor(Bitmap other) {
 			if (isSameCompressedBitmap(other)) {
 				bitset.xor(((CompressedBitmap) other).bitmap);
@@ -263,18 +288,22 @@ public class BitmapIndexImpl implements BitmapIndex {
 		}
 
 		/** @return the fully built immutable bitmap */
+		@Override
 		public CompressedBitmap build() {
 			return new CompressedBitmap(bitset.combine());
 		}
 
+		@Override
 		public Iterator<BitmapObject> iterator() {
 			return build().iterator();
 		}
 
+		@Override
 		public int cardinality() {
 			return bitset.combine().cardinality();
 		}
 
+		@Override
 		public boolean removeAllOrNone(PackBitmapIndex index) {
 			if (!packIndex.equals(index))
 				return false;
@@ -289,7 +318,8 @@ public class BitmapIndexImpl implements BitmapIndex {
 			return true;
 		}
 
-		BitmapIndexImpl getBitmapIndex() {
+		@Override
+		public BitmapIndexImpl getBitmapIndex() {
 			return BitmapIndexImpl.this;
 		}
 	}
@@ -301,14 +331,17 @@ public class BitmapIndexImpl implements BitmapIndex {
 			this.bitmap = bitmap;
 		}
 
+		@Override
 		public CompressedBitmap or(Bitmap other) {
 			return new CompressedBitmap(bitmap.or(bitmapOf(other)));
 		}
 
+		@Override
 		public CompressedBitmap andNot(Bitmap other) {
 			return new CompressedBitmap(bitmap.andNot(bitmapOf(other)));
 		}
 
+		@Override
 		public CompressedBitmap xor(Bitmap other) {
 			return new CompressedBitmap(bitmap.xor(bitmapOf(other)));
 		}
@@ -327,6 +360,7 @@ public class BitmapIndexImpl implements BitmapIndex {
 			return packIndex.ofObjectType(bitmap, type).intIterator();
 		}
 
+		@Override
 		public Iterator<BitmapObject> iterator() {
 			final IntIterator dynamic = bitmap.andNot(ones(indexObjectCount))
 					.intIterator();
@@ -419,7 +453,7 @@ public class BitmapIndexImpl implements BitmapIndex {
 			}
 		}
 
-		int addObject(AnyObjectId objectId, int type) {
+		int findOrInsert(AnyObjectId objectId, int type) {
 			MutableEntry entry = new MutableEntry(
 					objectId, type, revList.size());
 			revList.add(entry);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java
index e244de790b..50693d3392 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java
@@ -44,6 +44,7 @@
 package org.eclipse.jgit.internal.storage.pack;
 
 import static org.eclipse.jgit.internal.storage.file.PackBitmapIndex.FLAG_REUSE;
+import static org.eclipse.jgit.revwalk.RevFlag.SEEN;
 
 import java.io.IOException;
 import java.util.ArrayList;
@@ -72,10 +73,13 @@ import org.eclipse.jgit.revwalk.ObjectWalk;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevObject;
 import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.revwalk.filter.RevFilter;
 import org.eclipse.jgit.storage.pack.PackConfig;
 import org.eclipse.jgit.util.BlockList;
 import org.eclipse.jgit.util.SystemReader;
 
+import com.googlecode.javaewah.EWAHCompressedBitmap;
+
 /**
  * Helper class for the {@link PackWriter} to select commits for which to build
  * pack index bitmaps.
@@ -258,11 +262,8 @@ class PackWriterBitmapPreparer {
 				BitmapBuilder fullBitmap = commitBitmapIndex.newBitmapBuilder();
 				rw.reset();
 				rw.markStart(c);
-				for (AnyObjectId objectId : selectionHelper.reusedCommits) {
-					rw.markUninteresting(rw.parseCommit(objectId));
-				}
-				rw.setRevFilter(
-						PackWriterBitmapWalker.newRevFilter(null, fullBitmap));
+				rw.setRevFilter(PackWriterBitmapWalker.newRevFilter(
+						selectionHelper.reusedCommitsBitmap, fullBitmap));
 
 				while (rw.next() != null) {
 					// The RevFilter adds the reachable commits from this
@@ -311,6 +312,45 @@ class PackWriterBitmapPreparer {
 	}
 
 	/**
+	 * A RevFilter that excludes the commits named in a bitmap from the walk.
+	 * <p>
+	 * If a commit is in {@code bitmap} then that commit is not emitted by the
+	 * walk and its parents are marked as SEEN so the walk can skip them.  The
+	 * bitmaps passed in have the property that the parents of any commit in
+	 * {@code bitmap} are also in {@code bitmap}, so marking the parents as
+	 * SEEN speeds up the RevWalk by saving it from walking down blind alleys
+	 * and does not change the commits emitted.
+	 */
+	private static class NotInBitmapFilter extends RevFilter {
+		private final BitmapBuilder bitmap;
+
+		NotInBitmapFilter(BitmapBuilder bitmap) {
+			this.bitmap = bitmap;
+		}
+
+		@Override
+		public final boolean include(RevWalk rw, RevCommit c) {
+			if (!bitmap.contains(c)) {
+				return true;
+			}
+			for (RevCommit p : c.getParents()) {
+				p.add(SEEN);
+			}
+			return false;
+		}
+
+		@Override
+		public final NotInBitmapFilter clone() {
+			throw new UnsupportedOperationException();
+		}
+
+		@Override
+		public final boolean requiresCommitBody() {
+			return false;
+		}
+	}
+
+	/**
 	 * For each of the {@code want}s, which represent the tip commit of each
 	 * branch, set up an initial {@link BitmapBuilder}. Reuse previously built
 	 * bitmaps if possible.
@@ -346,12 +386,11 @@ class PackWriterBitmapPreparer {
 
 			RevCommit rc = (RevCommit) ro;
 			reuseCommits.add(new BitmapCommit(rc, false, entry.getFlags()));
-			rw.markUninteresting(rc);
-			// PackBitmapIndexRemapper.ofObjectType() ties the underlying
-			// bitmap in the old pack into the new bitmap builder.
-			bitmapRemapper.ofObjectType(bitmapRemapper.getBitmap(rc),
-					Constants.OBJ_COMMIT).trim();
-			reuse.add(rc, Constants.OBJ_COMMIT);
+			if (!reuse.contains(rc)) {
+				EWAHCompressedBitmap bitmap = bitmapRemapper.ofObjectType(
+						bitmapRemapper.getBitmap(rc), Constants.OBJ_COMMIT);
+				reuse.or(commitBitmapIndex.toBitmap(writeBitmaps, bitmap));
+			}
 		}
 
 		// Add branch tips that are not represented in old bitmap indices. Set
@@ -378,6 +417,7 @@ class PackWriterBitmapPreparer {
 		// Create a list of commits in reverse order (older to newer).
 		// For each branch that contains the commit, mark its parents as being
 		// in the bitmap.
+		rw.setRevFilter(new NotInBitmapFilter(reuse));
 		RevCommit[] commits = new RevCommit[expectedCommitCount];
 		int pos = commits.length;
 		RevCommit rc;
@@ -421,7 +461,7 @@ class PackWriterBitmapPreparer {
 		}
 
 		return new CommitSelectionHelper(peeledWant, commits, pos,
-				orderedTipCommitBitmaps, reuseCommits);
+				orderedTipCommitBitmaps, reuse, reuseCommits);
 	}
 
 	/*-
@@ -522,6 +562,8 @@ class PackWriterBitmapPreparer {
 	private static final class CommitSelectionHelper implements Iterable<RevCommit> {
 		final Set<? extends ObjectId> peeledWants;
 		final List<BitmapBuilderEntry> tipCommitBitmaps;
+
+		final BitmapBuilder reusedCommitsBitmap;
 		final Iterable<BitmapCommit> reusedCommits;
 		final RevCommit[] commitsByOldest;
 		final int commitStartPos;
@@ -529,11 +571,13 @@ class PackWriterBitmapPreparer {
 		CommitSelectionHelper(Set<? extends ObjectId> peeledWant,
 				RevCommit[] commitsByOldest, int commitStartPos,
 				List<BitmapBuilderEntry> bitmapEntries,
+				BitmapBuilder reusedCommitsBitmap,
 				Iterable<BitmapCommit> reuse) {
 			this.peeledWants = peeledWant;
 			this.commitsByOldest = commitsByOldest;
 			this.commitStartPos = commitStartPos;
 			this.tipCommitBitmaps = bitmapEntries;
+			this.reusedCommitsBitmap = reusedCommitsBitmap;
 			this.reusedCommits = reuse;
 		}
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapWalker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapWalker.java
index debb2f2abc..cd18a9c5cd 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapWalker.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapWalker.java
@@ -116,7 +116,15 @@ final class PackWriterBitmapWalker {
 			while (walker.next() != null) {
 				// Iterate through all of the commits. The BitmapRevFilter does
 				// the work.
+				//
+				// filter.include returns true for commits that do not have
+				// a bitmap in bitmapIndex and are not reachable from a
+				// bitmap in bitmapIndex encountered earlier in the walk.
+				// Thus the number of commits returned by next() measures how
+				// much history was traversed without being able to make use
+				// of bitmaps.
 				pm.update(1);
+				countOfBitmapIndexMisses++;
 			}
 
 			RevObject ro;
@@ -124,7 +132,6 @@ final class PackWriterBitmapWalker {
 				bitmapResult.add(ro, ro.getType());
 				pm.update(1);
 			}
-			countOfBitmapIndexMisses += filter.getCountOfLoadedCommits();
 		}
 
 		return bitmapResult;
@@ -154,14 +161,11 @@ final class PackWriterBitmapWalker {
 	}
 
 	static abstract class BitmapRevFilter extends RevFilter {
-		private long countOfLoadedCommits;
-
 		protected abstract boolean load(RevCommit cmit);
 
 		@Override
 		public final boolean include(RevWalk walker, RevCommit cmit) {
 			if (load(cmit)) {
-				countOfLoadedCommits++;
 				return true;
 			}
 			for (RevCommit p : cmit.getParents())
@@ -178,9 +182,5 @@ final class PackWriterBitmapWalker {
 		public final boolean requiresCommitBody() {
 			return false;
 		}
-
-		long getCountOfLoadedCommits() {
-			return countOfLoadedCommits;
-		}
 	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BitmapIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BitmapIndex.java
index 3c0e2c128e..037d3fd2a9 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BitmapIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BitmapIndex.java
@@ -125,7 +125,9 @@ public interface BitmapIndex {
 		 * @param type
 		 *            the Git object type. See {@link Constants}.
 		 * @return true if the value was not contained or able to be loaded.
+		 * @deprecated use {@link #or} or {@link #addObject} instead.
 		 */
+		@Deprecated
 		boolean add(AnyObjectId objectId, int type);
 
 		/**
@@ -138,6 +140,18 @@ public interface BitmapIndex {
 		boolean contains(AnyObjectId objectId);
 
 		/**
+		 * Adds the id to the bitmap.
+		 *
+		 * @param objectId
+		 *            the object ID
+		 * @param type
+		 *            the Git object type. See {@link Constants}.
+		 * @return the current builder.
+		 * @since 4.2
+		 */
+		BitmapBuilder addObject(AnyObjectId objectId, int type);
+
+		/**
 		 * Remove the id from the bitmap.
 		 *
 		 * @param objectId
@@ -190,5 +204,12 @@ public interface BitmapIndex {
 
 		/** @return the number of elements in the bitmap. */
 		int cardinality();
+
+		/**
+		 * The BitmapIndex for this BitmapBuilder.
+		 *
+		 * @since 4.2
+		 */
+		BitmapIndex getBitmapIndex();
 	}
 }