diff options
14 files changed, 1078 insertions, 26 deletions
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties index 28e0a4cc67..18f33147ce 100644 --- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties +++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties @@ -25,10 +25,13 @@ badSectionEntry=Bad section entry: {0} bareRepositoryNoWorkdirAndIndex=Bare Repository has neither a working tree, nor an index base64InputNotProperlyPadded=Base64 input not properly padded. baseLengthIncorrect=base length incorrect +bitmapMissingObject=Bitmap at {0} is missing {1}. +bitmapsMustBePrepared=Bitmaps must be prepared before they may be written. blameNotCommittedYet=Not Committed Yet blobNotFound=Blob not found: {0} blobNotFoundForPath=Blob not found: {0} for path: {1} branchNameInvalid=Branch name {0} is not allowed +buildingBitmaps=Building bitmaps cachedPacksPreventsIndexCreation=Using cached packs prevents index creation cachedPacksPreventsListingObjects=Using cached packs prevents listing objects cannotBeCombined=Cannot be combined. @@ -426,6 +429,7 @@ rewinding=Rewinding to commit {0} searchForReuse=Finding sources searchForSizes=Getting sizes secondsAgo={0} seconds ago +selectingCommits=Selecting commits sequenceTooLargeForDiffAlgorithm=Sequence too large for difference algorithm. serviceNotEnabledNoName=Service not enabled serviceNotPermitted={0} not permitted diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java index 388e0d325f..7a1efe89df 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java @@ -87,10 +87,13 @@ public class JGitText extends TranslationBundle { /***/ public String bareRepositoryNoWorkdirAndIndex; /***/ public String base64InputNotProperlyPadded; /***/ public String baseLengthIncorrect; + /***/ public String bitmapMissingObject; + /***/ public String bitmapsMustBePrepared; /***/ public String blameNotCommittedYet; /***/ public String blobNotFound; /***/ public String blobNotFoundForPath; /***/ public String branchNameInvalid; + /***/ public String buildingBitmaps; /***/ public String cachedPacksPreventsIndexCreation; /***/ public String cachedPacksPreventsListingObjects; /***/ public String cannotBeCombined; @@ -488,6 +491,7 @@ public class JGitText extends TranslationBundle { /***/ public String searchForReuse; /***/ public String searchForSizes; /***/ public String secondsAgo; + /***/ public String selectingCommits; /***/ public String sequenceTooLargeForDiffAlgorithm; /***/ public String serviceNotEnabledNoName; /***/ public String serviceNotPermitted; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java index 85982c7a0a..c767c033e5 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevFlag.java @@ -66,6 +66,16 @@ public class RevFlag { public static final RevFlag UNINTERESTING = new StaticRevFlag( "UNINTERESTING", RevWalk.UNINTERESTING); //$NON-NLS-1$ + /** + * Set on RevCommit instances added to {@link RevWalk#pending} queue. + * <p> + * We use this flag to avoid adding the same commit instance twice to our + * queue, especially if we reached it by more than one path. + * <p> + * This is a static flag. Its RevWalk is not available. + */ + public static final RevFlag SEEN = new StaticRevFlag("SEEN", RevWalk.SEEN); + final RevWalk walker; final String name; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java index 455f1bbd99..6d131abe19 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/dfs/DfsReader.java @@ -76,6 +76,7 @@ import org.eclipse.jgit.lib.AnyObjectId; import org.eclipse.jgit.lib.AsyncObjectLoaderQueue; import org.eclipse.jgit.lib.AsyncObjectSizeQueue; import org.eclipse.jgit.lib.BitmapIndex; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; import org.eclipse.jgit.lib.Constants; import org.eclipse.jgit.lib.InflaterCache; import org.eclipse.jgit.lib.ObjectId; @@ -152,6 +153,17 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { return null; } + public Collection<CachedPack> getCachedPacksAndUpdate( + BitmapBuilder needBitmap) throws IOException { + for (DfsPackFile pack : db.getPacks()) { + PackBitmapIndex bitmapIndex = pack.getPackBitmapIndex(this); + if (needBitmap.removeAllOrNone(bitmapIndex)) + return Collections.<CachedPack> singletonList( + new DfsCachedPack(pack)); + } + return Collections.emptyList(); + } + @Override public Collection<ObjectId> resolve(AbbreviatedObjectId id) throws IOException { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java index 82503b6d1e..c0e47eea12 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LocalCachedPack.java @@ -77,6 +77,13 @@ class LocalCachedPack extends CachedPack { this.packNames = packNames.toArray(new String[packNames.size()]); } + LocalCachedPack(List<PackFile> packs) { + odb = null; + tips = null; + packNames = null; + this.packs = packs.toArray(new PackFile[packs.size()]); + } + @Override public Set<ObjectId> getTips() { return tips; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java new file mode 100644 index 0000000000..1bc90c6df4 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexRemapper.java @@ -0,0 +1,197 @@ +/* + * Copyright (C) 2013, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.storage.file; + +import java.util.Collections; +import java.util.Iterator; + +import javaewah.EWAHCompressedBitmap; +import javaewah.IntIterator; + +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.BitmapIndex; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ObjectIdOwnerMap; +import org.eclipse.jgit.storage.file.BasePackBitmapIndex.StoredBitmap; + +/** + * A PackBitmapIndex that remaps the bitmaps in the previous index to the + * positions in the new pack index. Note, unlike typical PackBitmapIndex + * implementations this implementation is not thread safe, as it is intended to + * be used with a PackBitmapIndexBuilder, which is also not thread safe. + */ +public class PackBitmapIndexRemapper extends PackBitmapIndex + implements Iterable<PackBitmapIndexRemapper.Entry> { + + private final BasePackBitmapIndex oldPackIndex; + private final PackBitmapIndex newPackIndex; + private final ObjectIdOwnerMap<StoredBitmap> convertedBitmaps; + private final BitSet inflated; + private final int[] prevToNewMapping; + + /** + * A PackBitmapIndex that maps the positions in the prevBitmapIndex to the + * ones in the newIndex. + * + * @param prevBitmapIndex + * the bitmap index with the old mapping. + * @param newIndex + * the bitmap index with the new mapping. + * @return a bitmap index that attempts to do the mapping between the two. + */ + public static PackBitmapIndexRemapper newPackBitmapIndex( + BitmapIndex prevBitmapIndex, PackBitmapIndex newIndex) { + if (!(prevBitmapIndex instanceof BitmapIndexImpl)) + return new PackBitmapIndexRemapper(newIndex); + + PackBitmapIndex prevIndex = ((BitmapIndexImpl) prevBitmapIndex) + .getPackBitmapIndex(); + if (!(prevIndex instanceof BasePackBitmapIndex)) + return new PackBitmapIndexRemapper(newIndex); + + return new PackBitmapIndexRemapper( + (BasePackBitmapIndex) prevIndex, newIndex); + } + + private PackBitmapIndexRemapper(PackBitmapIndex newPackIndex) { + this.oldPackIndex = null; + this.newPackIndex = newPackIndex; + this.convertedBitmaps = null; + this.inflated = null; + this.prevToNewMapping = null; + } + + private PackBitmapIndexRemapper( + BasePackBitmapIndex oldPackIndex, PackBitmapIndex newPackIndex) { + this.oldPackIndex = oldPackIndex; + this.newPackIndex = newPackIndex; + convertedBitmaps = new ObjectIdOwnerMap<StoredBitmap>(); + inflated = new BitSet(newPackIndex.getObjectCount()); + + prevToNewMapping = new int[oldPackIndex.getObjectCount()]; + for (int pos = 0; pos < prevToNewMapping.length; pos++) + prevToNewMapping[pos] = newPackIndex.findPosition( + oldPackIndex.getObject(pos)); + } + + @Override + public int findPosition(AnyObjectId objectId) { + return newPackIndex.findPosition(objectId); + } + + @Override + public ObjectId getObject(int position) throws IllegalArgumentException { + return newPackIndex.getObject(position); + } + + @Override + public int getObjectCount() { + return newPackIndex.getObjectCount(); + } + + @Override + public EWAHCompressedBitmap ofObjectType( + EWAHCompressedBitmap bitmap, int type) { + return newPackIndex.ofObjectType(bitmap, type); + } + + public Iterator<Entry> iterator() { + if (oldPackIndex == null) + return Collections.<Entry> emptyList().iterator(); + + final Iterator<StoredBitmap> it = oldPackIndex.getBitmaps().iterator(); + return new Iterator<Entry>() { + public boolean hasNext() { + return it.hasNext(); + } + + public Entry next() { + StoredBitmap sb = it.next(); + return new Entry(sb, sb.getFlags()); + } + + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + + @Override + public EWAHCompressedBitmap getBitmap(AnyObjectId objectId) { + EWAHCompressedBitmap bitmap = newPackIndex.getBitmap(objectId); + if (bitmap != null || oldPackIndex == null) + return bitmap; + + StoredBitmap stored = convertedBitmaps.get(objectId); + if (stored != null) + return stored.getBitmap(); + + StoredBitmap oldBitmap = oldPackIndex.getBitmaps().get(objectId); + if (oldBitmap == null) + return null; + + inflated.clear(); + for (IntIterator i = oldBitmap.getBitmap().intIterator(); i.hasNext();) + inflated.set(prevToNewMapping[i.next()]); + bitmap = inflated.toEWAHCompressedBitmap(); + convertedBitmaps.add( + new StoredBitmap(objectId, bitmap, null, oldBitmap.getFlags())); + return bitmap; + } + + /** An entry in the old PackBitmapIndex. */ + public final class Entry extends ObjectId { + private final int flags; + + private Entry(AnyObjectId src, int flags) { + super(src); + this.flags = flags; + } + + /** @return the flags associated with the bitmap. */ + public int getFlags() { + return flags; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java index 8636eb3151..8ea4d15e5a 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackBitmapIndexWriterV1.java @@ -62,11 +62,17 @@ import org.eclipse.jgit.util.io.SafeBufferedOutputStream; * * @see PackBitmapIndexV1 */ -class PackBitmapIndexWriterV1 { +public class PackBitmapIndexWriterV1 { private final DigestOutputStream out; private final DataOutput dataOutput; - PackBitmapIndexWriterV1(final OutputStream dst) { + /** + * Creates the version 1 pack bitmap index files. + * + * @param dst + * the output stream to which the index will be written. + */ + public PackBitmapIndexWriterV1(final OutputStream dst) { out = new DigestOutputStream(dst instanceof BufferedOutputStream ? dst : new SafeBufferedOutputStream(dst), Constants.newMessageDigest()); @@ -140,7 +146,7 @@ class PackBitmapIndexWriterV1 { } private void writeBitmapEntry(StoredEntry entry) throws IOException { - // Write object, xor offset, and bitmap + // Write object, XOR offset, and bitmap dataOutput.writeInt((int) entry.getObjectId()); out.write(entry.getXorOffset()); out.write(entry.getFlags()); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java index b78c5ae267..e1c2a3eba4 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/PackIndexWriter.java @@ -94,24 +94,44 @@ public abstract class PackIndexWriter { * @throws IllegalArgumentException * no recognized pack index version can support the supplied * objects. This is likely a bug in the implementation. + * @see #oldestPossibleFormat(List) */ - @SuppressWarnings("fallthrough") public static PackIndexWriter createOldestPossible(final OutputStream dst, final List<? extends PackedObjectInfo> objs) { - int version = 1; - LOOP: for (final PackedObjectInfo oe : objs) { - switch (version) { - case 1: - if (PackIndexWriterV1.canStore(oe)) - continue; - version = 2; - case 2: - break LOOP; - } + return createVersion(dst, oldestPossibleFormat(objs)); + } + + /** + * Return the oldest (most widely understood) index format. + * <p> + * This method selects an index format that can accurate describe the + * supplied objects and that will be the most compatible format with older + * Git implementations. + * <p> + * Index version 1 is widely recognized by all Git implementations, but + * index version 2 (and later) is not as well recognized as it was + * introduced more than a year later. Index version 1 can only be used if + * the resulting pack file is under 4 gigabytes in size; packs larger than + * that limit must use index version 2. + * + * @param objs + * the objects the caller needs to store in the index. Entries + * will be examined until a format can be conclusively selected. + * @return the index format. + * @throws IllegalArgumentException + * no recognized pack index version can support the supplied + * objects. This is likely a bug in the implementation. + */ + public static int oldestPossibleFormat( + final List<? extends PackedObjectInfo> objs) { + for (final PackedObjectInfo oe : objs) { + if (!PackIndexWriterV1.canStore(oe)) + return 2; } - return createVersion(dst, version); + return 1; } + /** * Create a new writer instance for a specific index format version. * diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java index 2af48edccb..d9906dec9e 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WindowCursor.java @@ -63,6 +63,7 @@ import org.eclipse.jgit.internal.JGitText; import org.eclipse.jgit.lib.AbbreviatedObjectId; import org.eclipse.jgit.lib.AnyObjectId; import org.eclipse.jgit.lib.BitmapIndex; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; import org.eclipse.jgit.lib.Constants; import org.eclipse.jgit.lib.InflaterCache; import org.eclipse.jgit.lib.ObjectId; @@ -113,6 +114,17 @@ final class WindowCursor extends ObjectReader implements ObjectReuseAsIs { return null; } + public Collection<CachedPack> getCachedPacksAndUpdate( + BitmapBuilder needBitmap) throws IOException { + for (PackFile pack : db.getPacks()) { + PackBitmapIndex index = pack.getBitmapIndex(); + if (needBitmap.removeAllOrNone(index)) + return Collections.<CachedPack> singletonList( + new LocalCachedPack(Collections.singletonList(pack))); + } + return Collections.emptyList(); + } + @Override public Collection<ObjectId> resolve(AbbreviatedObjectId id) throws IOException { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java index ed0294ed30..8816ca495b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/ObjectReuseAsIs.java @@ -50,6 +50,7 @@ import java.util.List; import org.eclipse.jgit.errors.MissingObjectException; import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException; import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; import org.eclipse.jgit.lib.ObjectReader; import org.eclipse.jgit.lib.ProgressMonitor; @@ -232,4 +233,22 @@ public interface ObjectReuseAsIs { */ public abstract void copyPackAsIs(PackOutputStream out, CachedPack pack, boolean validate) throws IOException; + + /** + * Obtain the available cached packs that match the bitmap and update + * the bitmap by removing the items that are in the CachedPack. + * <p> + * A cached pack has known starting points and may be sent entirely as-is, + * with almost no effort on the sender's part. + * + * @param needBitmap + * the bitmap that contains all of the objects the client wants. + * @return the available cached packs. + * @throws IOException + * the cached packs cannot be listed from the repository. + * Callers may choose to ignore this and continue as-if there + * were no cached packs. + */ + public Collection<CachedPack> getCachedPacksAndUpdate( + BitmapBuilder needBitmap) throws IOException; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java index 58ee985ff5..fdff23085b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java @@ -130,6 +130,13 @@ public class PackConfig { */ public static final int DEFAULT_INDEX_VERSION = 2; + /** + * Default value of the build bitmaps option: {@value} + * + * @see #setBuildBitmaps(boolean) + */ + public static final boolean DEFAULT_BUILD_BITMAPS = false; + private int compressionLevel = Deflater.DEFAULT_COMPRESSION; @@ -159,6 +166,8 @@ public class PackConfig { private int indexVersion = DEFAULT_INDEX_VERSION; + private boolean buildBitmaps = DEFAULT_BUILD_BITMAPS; + /** Create a default configuration. */ public PackConfig() { @@ -210,6 +219,7 @@ public class PackConfig { this.threads = cfg.threads; this.executor = cfg.executor; this.indexVersion = cfg.indexVersion; + this.buildBitmaps = cfg.buildBitmaps; } /** @@ -615,6 +625,33 @@ public class PackConfig { } /** + * True if writer is allowed to build bitmaps for indexes. + * + * Default setting: {@value #DEFAULT_BUILD_BITMAPS} + * + * @return true if delta base is the writer can choose to output an index + * with bitmaps. + */ + public boolean isBuildBitmaps() { + return buildBitmaps; + } + + /** + * Set writer to allow building bitmaps for supported pack files. + * + * Index files can include bitmaps to speed up future ObjectWalks. + * + * Default setting: {@value #DEFAULT_BUILD_BITMAPS} + * + * @param buildBitmaps + * boolean indicating whether bitmaps may be included in the + * index. + */ + public void setBuildBitmaps(boolean buildBitmaps) { + this.buildBitmaps = buildBitmaps; + } + + /** * Update properties by setting fields from the configuration. * * If a property's corresponding variable is not defined in the supplied @@ -646,5 +683,6 @@ public class PackConfig { setReuseObjects(rc.getBoolean("pack", "reuseobjects", isReuseObjects())); //$NON-NLS-1$ //$NON-NLS-2$ setDeltaCompress(rc.getBoolean( "pack", "deltacompression", isDeltaCompress())); //$NON-NLS-1$ //$NON-NLS-2$ + setBuildBitmaps(rc.getBoolean("pack", "buildbitmaps", isBuildBitmaps())); //$NON-NLS-1$ //$NON-NLS-2$ } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java index 77ebaf618b..470ffd343c 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java @@ -84,6 +84,9 @@ import org.eclipse.jgit.internal.JGitText; import org.eclipse.jgit.lib.AnyObjectId; import org.eclipse.jgit.lib.AsyncObjectSizeQueue; import org.eclipse.jgit.lib.BatchingProgressMonitor; +import org.eclipse.jgit.lib.BitmapIndex; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.lib.BitmapObject; import org.eclipse.jgit.lib.Constants; import org.eclipse.jgit.lib.NullProgressMonitor; import org.eclipse.jgit.lib.ObjectId; @@ -103,6 +106,8 @@ import org.eclipse.jgit.revwalk.RevObject; import org.eclipse.jgit.revwalk.RevSort; import org.eclipse.jgit.revwalk.RevTag; import org.eclipse.jgit.revwalk.RevTree; +import org.eclipse.jgit.storage.file.PackBitmapIndexBuilder; +import org.eclipse.jgit.storage.file.PackBitmapIndexWriterV1; import org.eclipse.jgit.storage.file.PackIndexWriter; import org.eclipse.jgit.util.BlockList; import org.eclipse.jgit.util.TemporaryBuffer; @@ -213,6 +218,9 @@ public class PackWriter { // edge objects for thin packs private List<ObjectToPack> edgeObjects = new BlockList<ObjectToPack>(); + // Objects the client is known to have already. + private BitmapBuilder haveObjects; + private List<CachedPack> cachedPacks = new ArrayList<CachedPack>(2); private Set<ObjectId> tagTargets = Collections.emptySet(); @@ -254,16 +262,22 @@ public class PackWriter { private boolean useCachedPacks; + private boolean useBitmaps; + private boolean ignoreMissingUninteresting = true; private boolean pruneCurrentObjectList; private boolean shallowPack; + private boolean canBuildBitmaps; + private int depth; private Collection<? extends ObjectId> unshallowObjects; + private PackBitmapIndexBuilder writeBitmaps; + /** * Create writer for specified repository. * <p> @@ -441,6 +455,19 @@ public class PackWriter { useCachedPacks = useCached; } + /** @return true to use bitmaps for ObjectWalks, if available. */ + public boolean isUseBitmaps() { + return useBitmaps; + } + + /** + * @param useBitmaps + * if set to true, bitmaps will be used when preparing a pack. + */ + public void setUseBitmaps(boolean useBitmaps) { + this.useBitmaps = useBitmaps; + } + /** * @return true to ignore objects that are uninteresting and also not found * on local disk; false to throw a {@link MissingObjectException} @@ -792,6 +819,25 @@ public class PackWriter { } /** + * Returns the index format version that will be written. + * <p> + * This method can only be invoked after + * {@link #writePack(ProgressMonitor, ProgressMonitor, OutputStream)} has + * been invoked and completed successfully. + * + * @return the index format version. + */ + public int getIndexVersion() { + int indexVersion = config.getIndexVersion(); + if (indexVersion <= 0) { + for (BlockList<ObjectToPack> objs : objectsLists) + indexVersion = Math.max(indexVersion, + PackIndexWriter.oldestPossibleFormat(objs)); + } + return indexVersion; + } + + /** * Create an index file to match the pack file just written. * <p> * This method can only be invoked after @@ -810,14 +856,34 @@ public class PackWriter { throw new IOException(JGitText.get().cachedPacksPreventsIndexCreation); long writeStart = System.currentTimeMillis(); - final List<ObjectToPack> list = sortByName(); - final PackIndexWriter iw; - int indexVersion = config.getIndexVersion(); - if (indexVersion <= 0) - iw = PackIndexWriter.createOldestPossible(indexStream, list); - else - iw = PackIndexWriter.createVersion(indexStream, indexVersion); - iw.write(list, packcsum); + final PackIndexWriter iw = PackIndexWriter.createVersion( + indexStream, getIndexVersion()); + iw.write(sortByName(), packcsum); + stats.timeWriting += System.currentTimeMillis() - writeStart; + } + + /** + * Create a bitmap index file to match the pack file just written. + * <p> + * This method can only be invoked after + * {@link #prepareBitmapIndex(ProgressMonitor, Set)} has been invoked and + * completed successfully. Writing a corresponding bitmap index is an + * optional feature that not all pack users may require. + * + * @param bitmapIndexStream + * output for the bitmap index data. Caller is responsible for + * closing this stream. + * @throws IOException + * the index data could not be written to the supplied stream. + */ + public void writeBitmapIndex(final OutputStream bitmapIndexStream) + throws IOException { + if (writeBitmaps == null) + throw new IOException(JGitText.get().bitmapsMustBePrepared); + + long writeStart = System.currentTimeMillis(); + final PackBitmapIndexWriterV1 iw = new PackBitmapIndexWriterV1(bitmapIndexStream); + iw.write(writeBitmaps, packcsum); stats.timeWriting += System.currentTimeMillis() - writeStart; } @@ -859,6 +925,9 @@ public class PackWriter { case WRITING: task = JGitText.get().writingObjects; break; + case BUILDING_BITMAPS: + task = JGitText.get().buildingBitmaps; + break; default: throw new IllegalArgumentException( MessageFormat.format(JGitText.get().illegalPackingPhase, phase)); @@ -1540,6 +1609,24 @@ public class PackWriter { stats.interestingObjects = Collections.unmodifiableSet(new HashSet<ObjectId>(want)); stats.uninterestingObjects = Collections.unmodifiableSet(new HashSet<ObjectId>(have)); + walker.setRetainBody(false); + + canBuildBitmaps = config.isBuildBitmaps() + && !shallowPack + && have.isEmpty() + && (excludeInPacks == null || excludeInPacks.length == 0); + if (!shallowPack && useBitmaps) { + BitmapIndex bitmapIndex = reader.getBitmapIndex(); + if (bitmapIndex != null) { + PackWriterBitmapWalker bitmapWalker = new PackWriterBitmapWalker( + walker, bitmapIndex, countingMonitor); + findObjectsToPackUsingBitmaps(bitmapWalker, want, have); + endPhase(countingMonitor); + stats.timeCounting = System.currentTimeMillis() - countingStart; + return; + } + } + List<ObjectId> all = new ArrayList<ObjectId>(want.size() + have.size()); all.addAll(want); all.addAll(have); @@ -1552,7 +1639,6 @@ public class PackWriter { final RevFlagSet keepOnRestart = new RevFlagSet(); keepOnRestart.add(inCachedPack); - walker.setRetainBody(false); walker.carry(include); int haveEst = have.size(); @@ -1761,6 +1847,34 @@ public class PackWriter { stats.timeCounting = System.currentTimeMillis() - countingStart; } + private void findObjectsToPackUsingBitmaps( + PackWriterBitmapWalker bitmapWalker, Set<? extends ObjectId> want, + Set<? extends ObjectId> have) + throws MissingObjectException, IncorrectObjectTypeException, + IOException { + BitmapBuilder haveBitmap = bitmapWalker.findObjects(have, null); + bitmapWalker.reset(); + BitmapBuilder wantBitmap = bitmapWalker.findObjects(want, haveBitmap); + BitmapBuilder needBitmap = wantBitmap.andNot(haveBitmap); + + if (useCachedPacks && reuseSupport != null + && (excludeInPacks == null || excludeInPacks.length == 0)) + cachedPacks.addAll( + reuseSupport.getCachedPacksAndUpdate(needBitmap)); + + for (BitmapObject obj : needBitmap) { + ObjectId objectId = obj.getObjectId(); + if (exclude(objectId)) { + needBitmap.remove(objectId); + continue; + } + addObject(objectId, obj.getType(), 0); + } + + if (thin) + haveObjects = haveBitmap; + } + private static void pruneEdgesFromObjectList(List<ObjectToPack> list) { final int size = list.size(); int src = 0; @@ -1892,7 +2006,7 @@ public class PackWriter { if (ptr != null && !ptr.isEdge()) { otp.setDeltaBase(ptr); otp.setReuseAsIs(); - } else if (thin && ptr != null && ptr.isEdge()) { + } else if (thin && have(ptr, baseId)) { otp.setDeltaBase(baseId); otp.setReuseAsIs(); } else { @@ -1920,6 +2034,75 @@ public class PackWriter { otp.select(next); } + private final boolean have(ObjectToPack ptr, AnyObjectId objectId) { + return (ptr != null && ptr.isEdge()) + || (haveObjects != null && haveObjects.contains(objectId)); + } + + /** + * Prepares the bitmaps to be written to the pack index. Bitmaps can be used + * to speed up fetches and clones by storing the entire object graph at + * selected commits. + * + * This method can only be invoked after + * {@link #writePack(ProgressMonitor, ProgressMonitor, OutputStream)} has + * been invoked and completed successfully. Writing a corresponding bitmap + * index is an optional feature that not all pack users may require. + * + * @param pm + * progress monitor to report bitmap building work. + * @param want + * collection of objects to be marked as interesting (start + * points of graph traversal). + * @return whether a bitmap index may be written. + * @throws IOException + * when some I/O problem occur during reading objects. + */ + public boolean prepareBitmapIndex( + ProgressMonitor pm, Set<? extends ObjectId> want) + throws IOException { + if (!canBuildBitmaps || getObjectCount() > Integer.MAX_VALUE + || !cachedPacks.isEmpty()) + return false; + + if (pm == null) + pm = NullProgressMonitor.INSTANCE; + + writeBitmaps = new PackBitmapIndexBuilder(sortByName()); + PackWriterBitmapPreparer bitmapPreparer = + new PackWriterBitmapPreparer(reader, writeBitmaps, pm, want); + + int numCommits = objectsLists[Constants.OBJ_COMMIT].size(); + Collection<PackWriterBitmapPreparer.BitmapCommit> selectedCommits = + bitmapPreparer.doCommitSelection(numCommits); + + beginPhase(PackingPhase.BUILDING_BITMAPS, pm, selectedCommits.size()); + + PackWriterBitmapWalker walker = bitmapPreparer.newBitmapWalker(); + AnyObjectId last = null; + for (PackWriterBitmapPreparer.BitmapCommit cmit : selectedCommits) { + if (cmit.isReuseWalker()) + walker.reset(); + else + walker = bitmapPreparer.newBitmapWalker(); + + BitmapBuilder bitmap = walker.findObjects( + Collections.singleton(cmit), null); + + if (last != null && cmit.isReuseWalker() && !bitmap.contains(last)) + throw new IllegalStateException(MessageFormat.format( + JGitText.get().bitmapMissingObject, cmit.name(), + last.name())); + last = cmit; + writeBitmaps.addBitmap(cmit, bitmap.build(), cmit.getFlags()); + + pm.update(1); + } + + endPhase(pm); + return true; + } + private boolean reuseDeltaFor(ObjectToPack otp) { switch (otp.getType()) { case Constants.OBJ_COMMIT: @@ -2296,7 +2479,10 @@ public class PackWriter { COMPRESSING, /** Writing objects phase. */ - WRITING; + WRITING, + + /** Building bitmaps phase. */ + BUILDING_BITMAPS; } /** Summary of the current state of a PackWriter. */ diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java new file mode 100644 index 0000000000..11b2eccee0 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapPreparer.java @@ -0,0 +1,373 @@ +/* + * Copyright (C) 2012, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.storage.pack; + +import static org.eclipse.jgit.storage.file.PackBitmapIndex.FLAG_REUSE; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import javaewah.EWAHCompressedBitmap; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ObjectReader; +import org.eclipse.jgit.lib.ProgressMonitor; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +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.storage.file.BitmapIndexImpl; +import org.eclipse.jgit.storage.file.PackBitmapIndex; +import org.eclipse.jgit.storage.file.PackBitmapIndexBuilder; +import org.eclipse.jgit.storage.file.PackBitmapIndexRemapper; +import org.eclipse.jgit.util.BlockList; + +/** Helper class for the PackWriter to select commits for pack index bitmaps. */ +class PackWriterBitmapPreparer { + + private static final Comparator<BitmapBuilder> BUILDER_BY_CARDINALITY_DSC = + new Comparator<BitmapBuilder>() { + public int compare(BitmapBuilder a, BitmapBuilder b) { + return Integer.signum(b.cardinality() - a.cardinality()); + } + }; + + private final ObjectReader reader; + private final ProgressMonitor pm; + private final Set<? extends ObjectId> want; + private final PackBitmapIndexBuilder writeBitmaps; + private final BitmapIndexImpl commitBitmapIndex; + private final PackBitmapIndexRemapper bitmapRemapper; + private final BitmapIndexImpl bitmapIndex; + private final int minCommits = 100; + private final int maxCommits = 5000; + + PackWriterBitmapPreparer(ObjectReader reader, + PackBitmapIndexBuilder writeBitmaps, ProgressMonitor pm, + Set<? extends ObjectId> want) throws IOException { + this.reader = reader; + this.writeBitmaps = writeBitmaps; + this.pm = pm; + this.want = want; + this.commitBitmapIndex = new BitmapIndexImpl(writeBitmaps); + this.bitmapRemapper = PackBitmapIndexRemapper.newPackBitmapIndex( + reader.getBitmapIndex(), writeBitmaps); + this.bitmapIndex = new BitmapIndexImpl(bitmapRemapper); + } + + Collection<BitmapCommit> doCommitSelection(int expectedNumCommits) + throws MissingObjectException, IncorrectObjectTypeException, + IOException { + pm.beginTask(JGitText.get().selectingCommits, ProgressMonitor.UNKNOWN); + RevWalk rw = new RevWalk(reader); + WalkResult result = findPaths(rw, expectedNumCommits); + pm.endTask(); + + int totCommits = result.commitsByOldest.length - result.commitStartPos; + BlockList<BitmapCommit> selections = new BlockList<BitmapCommit>( + totCommits / minCommits + 1); + for (BitmapCommit reuse : result.reuse) + selections.add(reuse); + + if (totCommits == 0) { + for (AnyObjectId id : result.peeledWant) + selections.add(new BitmapCommit(id, false, 0)); + return selections; + } + + pm.beginTask(JGitText.get().selectingCommits, totCommits); + + for (BitmapBuilder bitmapableCommits : result.paths) { + int cardinality = bitmapableCommits.cardinality(); + + List<List<BitmapCommit>> running = new ArrayList< + List<BitmapCommit>>(); + + // Insert bitmaps at the offsets suggested by the + // nextSelectionDistance() heuristic. + int index = -1; + int nextIn = nextSelectionDistance(0, cardinality); + int nextFlg = nextIn == maxCommits ? PackBitmapIndex.FLAG_REUSE : 0; + boolean mustPick = nextIn == 0; + for (RevCommit c : result) { + if (!bitmapableCommits.contains(c)) + continue; + + index++; + nextIn--; + pm.update(1); + + // Always pick the items in want and prefer merge commits. + if (result.peeledWant.remove(c)) { + if (nextIn > 0) + nextFlg = 0; + } else if (!mustPick && ((nextIn > 0) + || (c.getParentCount() <= 1 && nextIn > -minCommits))) { + continue; + } + + int flags = nextFlg; + nextIn = nextSelectionDistance(index, cardinality); + nextFlg = nextIn == maxCommits ? PackBitmapIndex.FLAG_REUSE : 0; + mustPick = nextIn == 0; + + BitmapBuilder fullBitmap = commitBitmapIndex.newBitmapBuilder(); + rw.reset(); + rw.markStart(c); + for (AnyObjectId objectId : result.reuse) + rw.markUninteresting(rw.parseCommit(objectId)); + rw.setRevFilter( + PackWriterBitmapWalker.newRevFilter(null, fullBitmap)); + + while (rw.next() != null) { + // Work is done in the RevFilter. + } + + List<List<BitmapCommit>> matches = new ArrayList< + List<BitmapCommit>>(); + for (List<BitmapCommit> list : running) { + BitmapCommit last = list.get(list.size() - 1); + if (fullBitmap.contains(last)) + matches.add(list); + } + + List<BitmapCommit> match; + if (matches.isEmpty()) { + match = new ArrayList<BitmapCommit>(); + running.add(match); + } else { + match = matches.get(0); + // Append to longest + for (List<BitmapCommit> list : matches) { + if (list.size() > match.size()) + match = list; + } + } + match.add(new BitmapCommit(c, !match.isEmpty(), flags)); + writeBitmaps.addBitmap(c, fullBitmap, 0); + } + + for (List<BitmapCommit> list : running) + selections.addAll(list); + } + writeBitmaps.clearBitmaps(); // Remove the temporary commit bitmaps. + + // Add the remaining peeledWant + for (AnyObjectId remainingWant : result.peeledWant) + selections.add(new BitmapCommit(remainingWant, false, 0)); + + pm.endTask(); + return selections; + } + + private WalkResult findPaths(RevWalk rw, int expectedNumCommits) + throws MissingObjectException, IOException { + BitmapBuilder reuseBitmap = commitBitmapIndex.newBitmapBuilder(); + List<BitmapCommit> reuse = new ArrayList<BitmapCommit>(); + for (PackBitmapIndexRemapper.Entry entry : bitmapRemapper) { + if ((entry.getFlags() & FLAG_REUSE) != FLAG_REUSE) + continue; + + RevObject ro = rw.peel(rw.parseAny(entry)); + if (ro instanceof RevCommit) { + RevCommit rc = (RevCommit) ro; + reuse.add(new BitmapCommit(rc, false, entry.getFlags())); + rw.markUninteresting(rc); + + EWAHCompressedBitmap bitmap = bitmapRemapper.ofObjectType( + bitmapRemapper.getBitmap(rc), Constants.OBJ_COMMIT); + writeBitmaps.addBitmap(rc, bitmap, 0); + reuseBitmap.add(rc, Constants.OBJ_COMMIT); + } + } + writeBitmaps.clearBitmaps(); // Remove temporary bitmaps + + // Do a RevWalk by commit time descending. Keep track of all the paths + // from the wants. + List<BitmapBuilder> paths = new ArrayList<BitmapBuilder>(want.size()); + Set<RevCommit> peeledWant = new HashSet<RevCommit>(want.size()); + for (AnyObjectId objectId : want) { + RevObject ro = rw.peel(rw.parseAny(objectId)); + if (ro instanceof RevCommit && !reuseBitmap.contains(ro)) { + RevCommit rc = (RevCommit) ro; + peeledWant.add(rc); + rw.markStart(rc); + + BitmapBuilder bitmap = commitBitmapIndex.newBitmapBuilder(); + bitmap.or(reuseBitmap); + bitmap.add(rc, Constants.OBJ_COMMIT); + paths.add(bitmap); + } + } + + // Update the paths from the wants and create a list of commits in + // reverse iteration order. + RevCommit[] commits = new RevCommit[expectedNumCommits]; + int pos = commits.length; + RevCommit rc; + while ((rc = rw.next()) != null) { + commits[--pos] = rc; + for (BitmapBuilder path : paths) { + if (path.contains(rc)) { + for (RevCommit c : rc.getParents()) + path.add(c, Constants.OBJ_COMMIT); + } + } + + pm.update(1); + } + + // Remove the reused bitmaps from the paths + if (!reuse.isEmpty()) + for (BitmapBuilder bitmap : paths) + bitmap.andNot(reuseBitmap); + + // Sort the paths + List<BitmapBuilder> distinctPaths = new ArrayList<BitmapBuilder>(paths.size()); + while (!paths.isEmpty()) { + Collections.sort(paths, BUILDER_BY_CARDINALITY_DSC); + BitmapBuilder largest = paths.remove(0); + distinctPaths.add(largest); + + // Update the remaining paths, by removing the objects from + // the path that was just added. + for (int i = paths.size() - 1; i >= 0; i--) + paths.get(i).andNot(largest); + } + + return new WalkResult(peeledWant, commits, pos, distinctPaths, reuse); + } + + private int nextSelectionDistance(int idx, int cardinality) { + if (idx > cardinality) + throw new IllegalArgumentException(); + int idxFromStart = cardinality - idx; + int mustRegionEnd = 100; + if (idxFromStart <= mustRegionEnd) + return 0; + + // Commits more toward the start will have more bitmaps. + int minRegionEnd = 20000; + if (idxFromStart <= minRegionEnd) + return Math.min(idxFromStart - mustRegionEnd, minCommits); + + // Commits more toward the end will have fewer. + int next = Math.min(idxFromStart - minRegionEnd, maxCommits); + return Math.max(next, minCommits); + } + + PackWriterBitmapWalker newBitmapWalker() { + return new PackWriterBitmapWalker( + new ObjectWalk(reader), bitmapIndex, null); + } + + static final class BitmapCommit extends ObjectId { + private final boolean reuseWalker; + private final int flags; + + private BitmapCommit( + AnyObjectId objectId, boolean reuseWalker, int flags) { + super(objectId); + this.reuseWalker = reuseWalker; + this.flags = flags; + } + + boolean isReuseWalker() { + return reuseWalker; + } + + int getFlags() { + return flags; + } + } + + private static final class WalkResult implements Iterable<RevCommit> { + private final Set<? extends ObjectId> peeledWant; + private final RevCommit[] commitsByOldest; + private final int commitStartPos; + private final List<BitmapBuilder> paths; + private final Iterable<BitmapCommit> reuse; + + private WalkResult(Set<? extends ObjectId> peeledWant, + RevCommit[] commitsByOldest, int commitStartPos, + List<BitmapBuilder> paths, Iterable<BitmapCommit> reuse) { + this.peeledWant = peeledWant; + this.commitsByOldest = commitsByOldest; + this.commitStartPos = commitStartPos; + this.paths = paths; + this.reuse = reuse; + } + + public Iterator<RevCommit> iterator() { + return new Iterator<RevCommit>() { + int pos = commitStartPos; + + public boolean hasNext() { + return pos < commitsByOldest.length; + } + + public RevCommit next() { + return commitsByOldest[pos++]; + } + + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java new file mode 100644 index 0000000000..ced1fe4b82 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriterBitmapWalker.java @@ -0,0 +1,164 @@ +/* + * Copyright (C) 2012, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.storage.pack; + +import java.io.IOException; +import java.util.Set; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.lib.BitmapIndex; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.NullProgressMonitor; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.BitmapIndex.Bitmap; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.lib.ProgressMonitor; +import org.eclipse.jgit.revwalk.ObjectWalk; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevFlag; +import org.eclipse.jgit.revwalk.RevObject; +import org.eclipse.jgit.revwalk.RevWalk; +import org.eclipse.jgit.revwalk.filter.RevFilter; + +/** Helper class for PackWriter to do ObjectWalks with pack index bitmaps. */ +final class PackWriterBitmapWalker { + + private final ObjectWalk walker; + + private final BitmapIndex bitmapIndex; + + private final ProgressMonitor pm; + + PackWriterBitmapWalker( + ObjectWalk walker, BitmapIndex bitmapIndex, ProgressMonitor pm) { + this.walker = walker; + this.bitmapIndex = bitmapIndex; + this.pm = (pm == null) ? NullProgressMonitor.INSTANCE : pm; + } + + BitmapBuilder findObjects(Set<? extends ObjectId> start, BitmapBuilder seen) + throws MissingObjectException, IncorrectObjectTypeException, + IOException { + final BitmapBuilder bitmapResult = bitmapIndex.newBitmapBuilder(); + + for (ObjectId obj : start) { + Bitmap bitmap = bitmapIndex.getBitmap(obj); + if (bitmap != null) + bitmapResult.or(bitmap); + } + + boolean marked = false; + for (ObjectId obj : start) { + if (!bitmapResult.contains(obj)) { + walker.markStart(walker.parseAny(obj)); + marked = true; + } + } + + if (marked) { + walker.setRevFilter(newRevFilter(seen, bitmapResult)); + + while (walker.next() != null) { + // Iterate through all of the commits. The BitmapRevFilter does + // the work. + pm.update(1); + } + + RevObject ro; + while ((ro = walker.nextObject()) != null) { + bitmapResult.add(ro, ro.getType()); + pm.update(1); + } + } + + return bitmapResult; + } + + void reset() { + walker.reset(); + } + + static RevFilter newRevFilter( + final BitmapBuilder seen, final BitmapBuilder bitmapResult) { + if (seen != null) { + return new BitmapRevFilter() { + protected boolean load(RevCommit cmit) { + if (seen.contains(cmit)) + return false; + return bitmapResult.add(cmit, Constants.OBJ_COMMIT); + } + }; + } + return new BitmapRevFilter() { + @Override + protected boolean load(RevCommit cmit) { + return bitmapResult.add(cmit, Constants.OBJ_COMMIT); + } + }; + } + + static abstract class BitmapRevFilter extends RevFilter { + protected abstract boolean load(RevCommit cmit); + + @Override + public final boolean include(RevWalk walker, RevCommit cmit) { + if (load(cmit)) + return true; + for (RevCommit p : cmit.getParents()) + p.add(RevFlag.SEEN); + return false; + } + + @Override + public final RevFilter clone() { + return this; + } + + @Override + public final boolean requiresCommitBody() { + return false; + } + } +} |