Merge changes I6543c2e1,I21ed029d

* changes:
  ReceivePack: adding IterativeConnectivityChecker
  Moving transport/internal -> internal/transport

8 files changed, 416 insertions, 4 deletions

diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
index 6bd06e11b6..eda4505264 100644
--- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
@@ -42,6 +42,7 @@ Import-Package: com.googlecode.javaewah;version="[1.1.6,2.0.0)",
  org.eclipse.jgit.internal.storage.pack;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.storage.reftable;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.storage.reftree;version="[5.8.0,5.9.0)",
+ org.eclipse.jgit.internal.transport.connectivity;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.transport.http;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.internal.transport.parser;version="[5.8.0,5.9.0)",
  org.eclipse.jgit.junit;version="[5.8.0,5.9.0)",
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityCheckerTest.java
new file mode 100644
index 0000000000..e75dd22591
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityCheckerTest.java
@@ -0,0 +1,258 @@
+/*
+ * Copyright (c) 2019, Google LLC  and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * http://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.transport.connectivity;
+
+import static org.mockito.Mockito.doThrow;
+import static org.mockito.Mockito.verify;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.storage.dfs.DfsRepositoryDescription;
+import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.transport.PackParser;
+import org.eclipse.jgit.transport.ReceiveCommand;
+import org.eclipse.jgit.transport.ConnectivityChecker;
+import org.eclipse.jgit.transport.ConnectivityChecker.ConnectivityCheckInfo;
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.mockito.Mock;
+import org.mockito.junit.MockitoJUnit;
+import org.mockito.junit.MockitoRule;
+
+public class IterativeConnectivityCheckerTest {
+	@Rule
+	public MockitoRule rule = MockitoJUnit.rule();
+
+	private ObjectId branchHeadObjectId;
+
+	private ObjectId openRewiewObjectId;
+
+	private ObjectId newCommitObjectId;
+	private ObjectId otherHaveObjectId = ObjectId
+			.fromString("DEADBEEFDEADBEEFDEADBEEFDEADBEEFDEADBEEF");
+
+	private Set<ObjectId> advertisedHaves;
+
+	@Mock
+	private ConnectivityChecker connectivityCheckerDelegate;
+
+	@Mock
+	private ProgressMonitor pm;
+
+	@Mock
+	private PackParser parser;
+
+	private RevCommit branchHeadCommitObject;
+	private RevCommit openReviewCommitObject;
+	private RevCommit newCommitObject;
+
+	private ConnectivityCheckInfo connectivityCheckInfo;
+	private IterativeConnectivityChecker connectivityChecker;
+
+	private TestRepository tr;
+
+	@Before
+	public void setUp() throws Exception {
+		tr = new TestRepository<>(
+				new InMemoryRepository(new DfsRepositoryDescription("test")));
+		connectivityChecker = new IterativeConnectivityChecker(
+				connectivityCheckerDelegate);
+		connectivityCheckInfo = new ConnectivityCheckInfo();
+		connectivityCheckInfo.setParser(parser);
+		connectivityCheckInfo.setRepository(tr.getRepository());
+		connectivityCheckInfo.setWalk(tr.getRevWalk());
+
+		branchHeadCommitObject = tr.commit().create();
+		branchHeadObjectId = branchHeadCommitObject.getId();
+
+		openReviewCommitObject = tr.commit().create();
+		openRewiewObjectId = openReviewCommitObject.getId();
+
+		advertisedHaves = wrap(branchHeadObjectId, openRewiewObjectId,
+				otherHaveObjectId);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchBasedOnOld() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchBasedOnOldWithTip() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.setForcedHaves(wrap(openRewiewObjectId));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */,
+						openRewiewObjectId),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchMerge() throws Exception {
+		createNewCommit(branchHeadCommitObject, openReviewCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */,
+						openRewiewObjectId),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulNewBranchBasedOnNewWithTip() throws Exception {
+		createNewCommit();
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.setForcedHaves(wrap(openRewiewObjectId));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo, wrap(openRewiewObjectId), pm);
+	}
+
+	@Test
+	public void testSuccessfulPushOldBranch() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(pushOldBranchCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo, wrap(branchHeadObjectId /* as direct parent */),
+				pm);
+	}
+
+	@Test
+	public void testSuccessfulPushOldBranchMergeCommit() throws Exception {
+		createNewCommit(branchHeadCommitObject, openReviewCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(pushOldBranchCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate).checkConnectivity(
+				connectivityCheckInfo,
+				wrap(branchHeadObjectId /* as direct parent */,
+						openRewiewObjectId),
+				pm);
+	}
+
+
+	@Test
+	public void testNoChecksIfCantFindSubset() throws Exception {
+		createNewCommit();
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate)
+				.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	@Test
+	public void testReiterateInCaseNotSuccessful() throws Exception {
+		createNewCommit(branchHeadCommitObject);
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		doThrow(new MissingObjectException(branchHeadCommitObject,
+				Constants.OBJ_COMMIT)).when(connectivityCheckerDelegate)
+						.checkConnectivity(connectivityCheckInfo,
+								wrap(branchHeadObjectId /* as direct parent */), pm);
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate)
+				.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	@Test
+	public void testDependOnGrandparent() throws Exception {
+		RevCommit grandparent = tr.commit(new RevCommit[] {});
+		RevCommit parent = tr.commit(grandparent);
+		createNewCommit(parent);
+
+		branchHeadCommitObject = tr.commit(grandparent);
+		branchHeadObjectId = branchHeadCommitObject.getId();
+		tr.getRevWalk().dispose();
+
+		connectivityCheckInfo.setCommands(
+				Collections.singletonList(createNewBrachCommand()));
+
+		connectivityChecker.checkConnectivity(connectivityCheckInfo,
+				advertisedHaves, pm);
+
+		verify(connectivityCheckerDelegate)
+				.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	private static Set<ObjectId> wrap(ObjectId... objectIds) {
+		return new HashSet<>(Arrays.asList(objectIds));
+	}
+
+	private ReceiveCommand createNewBrachCommand() {
+		return new ReceiveCommand(ObjectId.zeroId(), newCommitObjectId,
+				"totally/a/new/branch");
+	}
+
+	private ReceiveCommand pushOldBranchCommand() {
+		return new ReceiveCommand(branchHeadObjectId, newCommitObjectId,
+				"push/to/an/old/branch");
+	}
+
+	private void createNewCommit(RevCommit... parents) throws Exception {
+		newCommitObject = tr.commit(parents);
+		newCommitObjectId = newCommitObject.getId();
+	}
+
+}
diff --git a/org.eclipse.jgit/META-INF/MANIFEST.MF b/org.eclipse.jgit/META-INF/MANIFEST.MF
index 2cb8ce21f3..5fb76f503f 100644
--- a/org.eclipse.jgit/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit/META-INF/MANIFEST.MF
@@ -86,6 +86,7 @@ Export-Package: org.eclipse.jgit.annotations;version="5.8.0",
    org.eclipse.jgit.pgm",
  org.eclipse.jgit.internal.storage.reftree;version="5.8.0";x-friends:="org.eclipse.jgit.junit,org.eclipse.jgit.test,org.eclipse.jgit.pgm",
  org.eclipse.jgit.internal.submodule;version="5.8.0";x-internal:=true,
+ org.eclipse.jgit.internal.transport.connectivity;version="5.8.0";x-friends:="org.eclipse.jgit.test",
  org.eclipse.jgit.internal.transport.http;version="5.8.0";x-friends:="org.eclipse.jgit.test",
  org.eclipse.jgit.internal.transport.parser;version="5.8.0";x-friends:="org.eclipse.jgit.http.server,org.eclipse.jgit.test",
  org.eclipse.jgit.internal.transport.ssh;version="5.8.0";x-friends:="org.eclipse.jgit.ssh.apache",
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/internal/FullConnectivityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/connectivity/FullConnectivityChecker.java
index 60d8f452ba..b76e3a3caa 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/internal/FullConnectivityChecker.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/connectivity/FullConnectivityChecker.java
@@ -8,7 +8,7 @@
  * SPDX-License-Identifier: BSD-3-Clause
  */
 
-package org.eclipse.jgit.transport.internal;
+package org.eclipse.jgit.internal.transport.connectivity;
 
 import java.io.IOException;
 import java.util.Set;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityChecker.java
new file mode 100644
index 0000000000..b44c4ae5cb
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/connectivity/IterativeConnectivityChecker.java
@@ -0,0 +1,152 @@
+/*
+ * Copyright (c) 2019, Google LLC  and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * http://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.internal.transport.connectivity;
+
+import static java.util.stream.Collectors.toList;
+
+import java.io.IOException;
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Queue;
+import java.util.Set;
+import java.util.stream.Stream;
+
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevObject;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.transport.ConnectivityChecker;
+import org.eclipse.jgit.transport.ReceiveCommand;
+
+/**
+ * Implementation of connectivity checker which tries to do check with smaller
+ * set of references first and if it fails will fall back to check against all
+ * advertised references.
+ *
+ * This is useful for big repos with enormous number of references.
+ */
+public class IterativeConnectivityChecker implements ConnectivityChecker {
+	private static final int MAXIMUM_PARENTS_TO_CHECK = 128;
+
+	private final ConnectivityChecker delegate;
+
+	private Set<ObjectId> forcedHaves = Collections.emptySet();
+
+	/**
+	 * @param delegate
+	 *            Delegate checker which will be called for actual checks.
+	 */
+	public IterativeConnectivityChecker(ConnectivityChecker delegate) {
+		this.delegate = delegate;
+	}
+
+	@Override
+	public void checkConnectivity(ConnectivityCheckInfo connectivityCheckInfo,
+			Set<ObjectId> advertisedHaves, ProgressMonitor pm)
+			throws MissingObjectException, IOException {
+		try {
+			Set<ObjectId> newRefs = new HashSet<>();
+			Set<ObjectId> expectedParents = new HashSet<>();
+
+			getAllObjectIds(connectivityCheckInfo.getCommands())
+					.forEach(oid -> {
+						if (advertisedHaves.contains(oid)) {
+							expectedParents.add(oid);
+						} else {
+							newRefs.add(oid);
+						}
+					});
+			if (!newRefs.isEmpty()) {
+				expectedParents.addAll(extractAdvertisedParentCommits(newRefs,
+						advertisedHaves, connectivityCheckInfo.getWalk()));
+			}
+
+			expectedParents.addAll(forcedHaves);
+
+			if (!expectedParents.isEmpty()) {
+				delegate.checkConnectivity(connectivityCheckInfo,
+						expectedParents, pm);
+				return;
+			}
+		} catch (MissingObjectException e) {
+			// This is fine, retry with all haves.
+		}
+		delegate.checkConnectivity(connectivityCheckInfo, advertisedHaves, pm);
+	}
+
+	private static Stream<ObjectId> getAllObjectIds(
+			List<ReceiveCommand> commands) {
+		return commands.stream().flatMap(cmd -> {
+			if (cmd.getType() == ReceiveCommand.Type.UPDATE || cmd
+					.getType() == ReceiveCommand.Type.UPDATE_NONFASTFORWARD) {
+				return Stream.of(cmd.getOldId(), cmd.getNewId());
+			} else if (cmd.getType() == ReceiveCommand.Type.CREATE) {
+				return Stream.of(cmd.getNewId());
+			}
+			return Stream.of();
+		});
+	}
+
+	/**
+	 * Sets additional haves that client can depend on (e.g. gerrit changes).
+	 *
+	 * @param forcedHaves
+	 *            Haves server expects client to depend on.
+	 */
+	public void setForcedHaves(Set<ObjectId> forcedHaves) {
+		this.forcedHaves = Collections.unmodifiableSet(forcedHaves);
+	}
+
+	private static Set<ObjectId> extractAdvertisedParentCommits(
+			Set<ObjectId> newRefs, Set<ObjectId> advertisedHaves, RevWalk rw)
+			throws MissingObjectException, IOException {
+		Set<ObjectId> advertisedParents = new HashSet<>();
+		for (ObjectId newRef : newRefs) {
+			RevObject object = rw.parseAny(newRef);
+			if (object instanceof RevCommit) {
+				int numberOfParentsToCheck = 0;
+				Queue<RevCommit> parents = new ArrayDeque<>(
+						MAXIMUM_PARENTS_TO_CHECK);
+				parents.addAll(
+						parseParents(((RevCommit) object).getParents(), rw));
+				// Looking through a chain of ancestors handles the case where a
+				// series of commits is sent in a single push for a new branch.
+				while (!parents.isEmpty()) {
+					RevCommit parentCommit = parents.poll();
+					if (advertisedHaves.contains(parentCommit.getId())) {
+						advertisedParents.add(parentCommit.getId());
+					} else if (numberOfParentsToCheck < MAXIMUM_PARENTS_TO_CHECK) {
+						RevCommit[] grandParents = parentCommit.getParents();
+						numberOfParentsToCheck += grandParents.length;
+						parents.addAll(parseParents(grandParents, rw));
+					}
+				}
+			}
+		}
+		return advertisedParents;
+	}
+
+	private static List<RevCommit> parseParents(RevCommit[] parents,
+			RevWalk rw) {
+		return Arrays.stream(parents).map((commit) -> {
+			try {
+				return rw.parseCommit(commit);
+			} catch (Exception e) {
+				throw new RuntimeException(e);
+			}
+		}).collect(toList());
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/internal/DelegatingSSLSocketFactory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/http/DelegatingSSLSocketFactory.java
index d25ecd459d..5aab61ad05 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/internal/DelegatingSSLSocketFactory.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/transport/http/DelegatingSSLSocketFactory.java
@@ -7,7 +7,7 @@
  *
  * SPDX-License-Identifier: BSD-3-Clause
  */
-package org.eclipse.jgit.transport.internal;
+package org.eclipse.jgit.internal.transport.http;
 
 import java.io.IOException;
 import java.net.InetAddress;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/ReceivePack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/ReceivePack.java
index 8a8c1ae0ba..49413e54f3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/ReceivePack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/ReceivePack.java
@@ -48,6 +48,7 @@ import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.internal.storage.file.PackLock;
 import org.eclipse.jgit.internal.submodule.SubmoduleValidator;
 import org.eclipse.jgit.internal.submodule.SubmoduleValidator.SubmoduleValidationException;
+import org.eclipse.jgit.internal.transport.connectivity.FullConnectivityChecker;
 import org.eclipse.jgit.internal.transport.parser.FirstCommand;
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.BatchRefUpdate;
@@ -72,7 +73,6 @@ import org.eclipse.jgit.transport.ConnectivityChecker.ConnectivityCheckInfo;
 import org.eclipse.jgit.transport.PacketLineIn.InputOverLimitIOException;
 import org.eclipse.jgit.transport.ReceiveCommand.Result;
 import org.eclipse.jgit.transport.RefAdvertiser.PacketLineOutRefAdvertiser;
-import org.eclipse.jgit.transport.internal.FullConnectivityChecker;
 import org.eclipse.jgit.util.io.InterruptTimer;
 import org.eclipse.jgit.util.io.LimitedInputStream;
 import org.eclipse.jgit.util.io.TimeoutInputStream;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/http/JDKHttpConnection.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/http/JDKHttpConnection.java
index 925c4e2f84..3b0bae21ef 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/http/JDKHttpConnection.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/http/JDKHttpConnection.java
@@ -32,7 +32,7 @@ import javax.net.ssl.SSLSocket;
 import javax.net.ssl.TrustManager;
 
 import org.eclipse.jgit.annotations.NonNull;
-import org.eclipse.jgit.transport.internal.DelegatingSSLSocketFactory;
+import org.eclipse.jgit.internal.transport.http.DelegatingSSLSocketFactory;
 import org.eclipse.jgit.util.HttpSupport;
 /**
  * A {@link org.eclipse.jgit.transport.http.HttpConnection} which simply