Prevent alternates loop

When looping through alternates, prevent visiting the same object
directory twice. This could happen when the objects/info/alternates file
includes itself directly or indirectly via a another repo and its
alternates file.

Change-Id: I79bb3da099ebc3c262d2e6c61ed4578eb1aa3474
Signed-off-by: James Melvin <jmelvin@codeaurora.org>
Signed-off-by: Martin Fick <mfick@codeaurora.org>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

3 files changed, 221 insertions, 63 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java
index d47b304688..ae8260a997 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java
@@ -47,8 +47,10 @@ package org.eclipse.jgit.internal.storage.file;
 import java.io.File;
 import java.io.IOException;
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.Set;
 
+import org.eclipse.jgit.internal.storage.file.ObjectDirectory.AlternateHandle;
 import org.eclipse.jgit.internal.storage.pack.ObjectToPack;
 import org.eclipse.jgit.internal.storage.pack.PackWriter;
 import org.eclipse.jgit.lib.AbbreviatedObjectId;
@@ -160,43 +162,70 @@ class CachedObjectDirectory extends FileObjectDatabase {
 		return alts;
 	}
 
+	private Set<AlternateHandle.Id> skipMe(Set<AlternateHandle.Id> skips) {
+		Set<AlternateHandle.Id> withMe = new HashSet<>();
+		if (skips != null) {
+			withMe.addAll(skips);
+		}
+		withMe.add(getAlternateId());
+		return withMe;
+	}
+
 	@Override
 	void resolve(Set<ObjectId> matches, AbbreviatedObjectId id)
 			throws IOException {
-		// In theory we could accelerate the loose object scan using our
-		// unpackedObjects map, but its not worth the huge code complexity.
-		// Scanning a single loose directory is fast enough, and this is
-		// unlikely to be called anyway.
-		//
 		wrapped.resolve(matches, id);
 	}
 
 	@Override
 	public boolean has(final AnyObjectId objectId) throws IOException {
-		if (unpackedObjects.contains(objectId))
+		return has(objectId, null);
+	}
+
+	private boolean has(final AnyObjectId objectId, Set<AlternateHandle.Id> skips)
+			throws IOException {
+		if (unpackedObjects.contains(objectId)) {
 			return true;
-		if (wrapped.hasPackedObject(objectId))
+		}
+		if (wrapped.hasPackedObject(objectId)) {
 			return true;
+		}
+		skips = skipMe(skips);
 		for (CachedObjectDirectory alt : myAlternates()) {
-			if (alt.has(objectId))
-				return true;
+			if (!skips.contains(alt.getAlternateId())) {
+				if (alt.has(objectId, skips)) {
+					return true;
+				}
+			}
 		}
 		return false;
 	}
 
 	@Override
-	ObjectLoader openObject(final WindowCursor curs,
-			final AnyObjectId objectId) throws IOException {
+	ObjectLoader openObject(final WindowCursor curs, final AnyObjectId objectId)
+			throws IOException {
+		return openObject(curs, objectId, null);
+	}
+
+	private ObjectLoader openObject(final WindowCursor curs,
+			final AnyObjectId objectId, Set<AlternateHandle.Id> skips)
+			throws IOException {
 		ObjectLoader ldr = openLooseObject(curs, objectId);
-		if (ldr != null)
+		if (ldr != null) {
 			return ldr;
+		}
 		ldr = wrapped.openPackedObject(curs, objectId);
-		if (ldr != null)
+		if (ldr != null) {
 			return ldr;
+		}
+		skips = skipMe(skips);
 		for (CachedObjectDirectory alt : myAlternates()) {
-			ldr = alt.openObject(curs, objectId);
-			if (ldr != null)
-				return ldr;
+			if (!skips.contains(alt.getAlternateId())) {
+				ldr = alt.openObject(curs, objectId, skips);
+				if (ldr != null) {
+					return ldr;
+				}
+			}
 		}
 		return null;
 	}
@@ -260,4 +289,8 @@ class CachedObjectDirectory extends FileObjectDatabase {
 			super(id);
 		}
 	}
+
+	private AlternateHandle.Id getAlternateId() {
+		return wrapped.getAlternateId();
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileRepository.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileRepository.java
index ba52251a4c..2fd49619d3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileRepository.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileRepository.java
@@ -490,10 +490,28 @@ public class FileRepository extends Repository {
 	 */
 	@Override
 	public Set<ObjectId> getAdditionalHaves() {
+		return getAdditionalHaves(null);
+	}
+
+	/**
+	 * Objects known to exist but not expressed by {@link #getAllRefs()}.
+	 * <p>
+	 * When a repository borrows objects from another repository, it can
+	 * advertise that it safely has that other repository's references, without
+	 * exposing any other details about the other repository.  This may help
+	 * a client trying to push changes avoid pushing more than it needs to.
+	 *
+	 * @param skips
+	 *            Set of AlternateHandle Ids already seen
+	 *
+	 * @return unmodifiable collection of other known objects.
+	 */
+	private Set<ObjectId> getAdditionalHaves(Set<AlternateHandle.Id> skips) {
 		HashSet<ObjectId> r = new HashSet<>();
+		skips = objectDatabase.addMe(skips);
 		for (AlternateHandle d : objectDatabase.myAlternates()) {
-			if (d instanceof AlternateRepository) {
-				Repository repo;
+			if (d instanceof AlternateRepository && !skips.contains(d.getId())) {
+				FileRepository repo;
 
 				repo = ((AlternateRepository) d).repository;
 				for (Ref ref : repo.getAllRefs().values()) {
@@ -502,7 +520,7 @@ public class FileRepository extends Repository {
 					if (ref.getPeeledObjectId() != null)
 						r.add(ref.getPeeledObjectId());
 				}
-				r.addAll(repo.getAdditionalHaves());
+				r.addAll(repo.getAdditionalHaves(skips));
 			}
 		}
 		return r;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java
index 00e39533b1..d953b87c4b 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java
@@ -64,6 +64,7 @@ import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -117,6 +118,8 @@ public class ObjectDirectory extends FileObjectDatabase {
 	/** Maximum number of candidates offered as resolutions of abbreviation. */
 	private static final int RESOLVE_ABBREV_LIMIT = 256;
 
+	private final AlternateHandle handle = new AlternateHandle(this);
+
 	private final Config config;
 
 	private final File objects;
@@ -294,26 +297,38 @@ public class ObjectDirectory extends FileObjectDatabase {
 	@Override
 	public boolean has(AnyObjectId objectId) {
 		return unpackedObjectCache.isUnpacked(objectId)
-				|| hasPackedInSelfOrAlternate(objectId)
-				|| hasLooseInSelfOrAlternate(objectId);
+				|| hasPackedInSelfOrAlternate(objectId, null)
+				|| hasLooseInSelfOrAlternate(objectId, null);
 	}
 
-	private boolean hasPackedInSelfOrAlternate(AnyObjectId objectId) {
-		if (hasPackedObject(objectId))
+	private boolean hasPackedInSelfOrAlternate(AnyObjectId objectId,
+			Set<AlternateHandle.Id> skips) {
+		if (hasPackedObject(objectId)) {
 			return true;
+		}
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			if (alt.db.hasPackedInSelfOrAlternate(objectId))
-				return true;
+			if (!skips.contains(alt.getId())) {
+				if (alt.db.hasPackedInSelfOrAlternate(objectId, skips)) {
+					return true;
+				}
+			}
 		}
 		return false;
 	}
 
-	private boolean hasLooseInSelfOrAlternate(AnyObjectId objectId) {
-		if (fileFor(objectId).exists())
+	private boolean hasLooseInSelfOrAlternate(AnyObjectId objectId,
+			Set<AlternateHandle.Id> skips) {
+		if (fileFor(objectId).exists()) {
 			return true;
+		}
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			if (alt.db.hasLooseInSelfOrAlternate(objectId))
-				return true;
+			if (!skips.contains(alt.getId())) {
+				if (alt.db.hasLooseInSelfOrAlternate(objectId, skips)) {
+					return true;
+				}
+			}
 		}
 		return false;
 	}
@@ -340,6 +355,12 @@ public class ObjectDirectory extends FileObjectDatabase {
 	@Override
 	void resolve(Set<ObjectId> matches, AbbreviatedObjectId id)
 			throws IOException {
+		resolve(matches, id, null);
+	}
+
+	private void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
+			Set<AlternateHandle.Id> skips)
+			throws IOException {
 		// Go through the packs once. If we didn't find any resolutions
 		// scan for new packs and check once more.
 		int oldSize = matches.size();
@@ -376,10 +397,14 @@ public class ObjectDirectory extends FileObjectDatabase {
 			}
 		}
 
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			alt.db.resolve(matches, id);
-			if (matches.size() > RESOLVE_ABBREV_LIMIT)
-				return;
+			if (!skips.contains(alt.getId())) {
+				alt.db.resolve(matches, id, skips);
+				if (matches.size() > RESOLVE_ABBREV_LIMIT) {
+					return;
+				}
+			}
 		}
 	}
 
@@ -388,37 +413,50 @@ public class ObjectDirectory extends FileObjectDatabase {
 			throws IOException {
 		if (unpackedObjectCache.isUnpacked(objectId)) {
 			ObjectLoader ldr = openLooseObject(curs, objectId);
-			if (ldr != null)
+			if (ldr != null) {
 				return ldr;
+			}
 		}
-		ObjectLoader ldr = openPackedFromSelfOrAlternate(curs, objectId);
-		if (ldr != null)
+		ObjectLoader ldr = openPackedFromSelfOrAlternate(curs, objectId, null);
+		if (ldr != null) {
 			return ldr;
-		return openLooseFromSelfOrAlternate(curs, objectId);
+		}
+		return openLooseFromSelfOrAlternate(curs, objectId, null);
 	}
 
 	private ObjectLoader openPackedFromSelfOrAlternate(WindowCursor curs,
-			AnyObjectId objectId) {
+			AnyObjectId objectId, Set<AlternateHandle.Id> skips) {
 		ObjectLoader ldr = openPackedObject(curs, objectId);
-		if (ldr != null)
+		if (ldr != null) {
 			return ldr;
+		}
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			ldr = alt.db.openPackedFromSelfOrAlternate(curs, objectId);
-			if (ldr != null)
-				return ldr;
+			if (!skips.contains(alt.getId())) {
+				ldr = alt.db.openPackedFromSelfOrAlternate(curs, objectId, skips);
+				if (ldr != null) {
+					return ldr;
+				}
+			}
 		}
 		return null;
 	}
 
 	private ObjectLoader openLooseFromSelfOrAlternate(WindowCursor curs,
-			AnyObjectId objectId) throws IOException {
+			AnyObjectId objectId, Set<AlternateHandle.Id> skips)
+					throws IOException {
 		ObjectLoader ldr = openLooseObject(curs, objectId);
-		if (ldr != null)
+		if (ldr != null) {
 			return ldr;
+		}
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			ldr = alt.db.openLooseFromSelfOrAlternate(curs, objectId);
-			if (ldr != null)
-				return ldr;
+			if (!skips.contains(alt.getId())) {
+				ldr = alt.db.openLooseFromSelfOrAlternate(curs, objectId, skips);
+				if (ldr != null) {
+					return ldr;
+				}
+			}
 		}
 		return null;
 	}
@@ -469,37 +507,49 @@ public class ObjectDirectory extends FileObjectDatabase {
 			throws IOException {
 		if (unpackedObjectCache.isUnpacked(id)) {
 			long len = getLooseObjectSize(curs, id);
-			if (0 <= len)
+			if (0 <= len) {
 				return len;
+			}
 		}
-		long len = getPackedSizeFromSelfOrAlternate(curs, id);
-		if (0 <= len)
+		long len = getPackedSizeFromSelfOrAlternate(curs, id, null);
+		if (0 <= len) {
 			return len;
-		return getLooseSizeFromSelfOrAlternate(curs, id);
+		}
+		return getLooseSizeFromSelfOrAlternate(curs, id, null);
 	}
 
 	private long getPackedSizeFromSelfOrAlternate(WindowCursor curs,
-			AnyObjectId id) {
+			AnyObjectId id, Set<AlternateHandle.Id> skips) {
 		long len = getPackedObjectSize(curs, id);
-		if (0 <= len)
+		if (0 <= len) {
 			return len;
+		}
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			len = alt.db.getPackedSizeFromSelfOrAlternate(curs, id);
-			if (0 <= len)
-				return len;
+			if (!skips.contains(alt.getId())) {
+				len = alt.db.getPackedSizeFromSelfOrAlternate(curs, id, skips);
+				if (0 <= len) {
+					return len;
+				}
+			}
 		}
 		return -1;
 	}
 
 	private long getLooseSizeFromSelfOrAlternate(WindowCursor curs,
-			AnyObjectId id) throws IOException {
+			AnyObjectId id, Set<AlternateHandle.Id> skips) throws IOException {
 		long len = getLooseObjectSize(curs, id);
-		if (0 <= len)
+		if (0 <= len) {
 			return len;
+		}
+		skips = addMe(skips);
 		for (AlternateHandle alt : myAlternates()) {
-			len = alt.db.getLooseSizeFromSelfOrAlternate(curs, id);
-			if (0 <= len)
-				return len;
+			if (!skips.contains(alt.getId())) {
+				len = alt.db.getLooseSizeFromSelfOrAlternate(curs, id, skips);
+				if (0 <= len) {
+					return len;
+				}
+			}
 		}
 		return -1;
 	}
@@ -546,7 +596,12 @@ public class ObjectDirectory extends FileObjectDatabase {
 
 	@Override
 	void selectObjectRepresentation(PackWriter packer, ObjectToPack otp,
-			WindowCursor curs) throws IOException {
+																	WindowCursor curs) throws IOException {
+		selectObjectRepresentation(packer, otp, curs, null);
+	}
+
+	private void selectObjectRepresentation(PackWriter packer, ObjectToPack otp,
+			WindowCursor curs, Set<AlternateHandle.Id> skips) throws IOException {
 		PackList pList = packList.get();
 		SEARCH: for (;;) {
 			for (final PackFile p : pList.packs) {
@@ -567,8 +622,12 @@ public class ObjectDirectory extends FileObjectDatabase {
 			break SEARCH;
 		}
 
-		for (AlternateHandle h : myAlternates())
-			h.db.selectObjectRepresentation(packer, otp, curs);
+		skips = addMe(skips);
+		for (AlternateHandle h : myAlternates()) {
+			if (!skips.contains(h.getId())) {
+				h.db.selectObjectRepresentation(packer, otp, curs, skips);
+			}
+		}
 	}
 
 	private void handlePackError(IOException e, PackFile p) {
@@ -930,6 +989,14 @@ public class ObjectDirectory extends FileObjectDatabase {
 		return alt;
 	}
 
+	Set<AlternateHandle.Id> addMe(Set<AlternateHandle.Id> skips) {
+		if (skips == null) {
+			skips = new HashSet<>();
+		}
+		skips.add(handle.getId());
+		return skips;
+	}
+
 	private AlternateHandle[] loadAlternates() throws IOException {
 		final List<AlternateHandle> l = new ArrayList<>(4);
 		final BufferedReader br = open(alternatesFile);
@@ -996,6 +1063,38 @@ public class ObjectDirectory extends FileObjectDatabase {
 	}
 
 	static class AlternateHandle {
+		static class Id {
+			String alternateId;
+
+			public Id(File object) {
+				try {
+					this.alternateId = object.getCanonicalPath();
+				} catch (Exception e) {
+					alternateId = null;
+				}
+			}
+
+			@Override
+			public boolean equals(Object o) {
+				if (o == this) {
+					return true;
+				}
+				if (o == null || !(o instanceof Id)) {
+					return false;
+				}
+				Id aId = (Id) o;
+				return Objects.equals(alternateId, aId.alternateId);
+			}
+
+			@Override
+			public int hashCode() {
+				if (alternateId == null) {
+					return 1;
+				}
+				return alternateId.hashCode();
+			}
+		}
+
 		final ObjectDirectory db;
 
 		AlternateHandle(ObjectDirectory db) {
@@ -1005,6 +1104,10 @@ public class ObjectDirectory extends FileObjectDatabase {
 		void close() {
 			db.close();
 		}
+
+		public Id getId(){
+			return db.getAlternateId();
+		}
 	}
 
 	static class AlternateRepository extends AlternateHandle {
@@ -1029,4 +1132,8 @@ public class ObjectDirectory extends FileObjectDatabase {
 	CachedObjectDirectory newCachedFileObjectDatabase() {
 		return new CachedObjectDirectory(this);
 	}
+
+	AlternateHandle.Id getAlternateId() {
+		return new AlternateHandle.Id(objects);
+	}
 }