From dbd05433ecc77d8044e567f512bb721ff259d7f8 Mon Sep 17 00:00:00 2001 From: Terry Parker Date: Sun, 24 Jan 2021 22:18:21 -0800 Subject: Move reachability checker generation into the ObjectReader object Reachability checkers are retrieved from RevWalk and ObjectWalk objects: * RevWalk.createReachabilityChecker() * ObjectWalk.createObjectReachabilityChecker() Since RevWalks and ObjectWalks are themselves directly instantiated in hundreds of places (e.g. UploadPack...) overriding them in a consistent way requires overloading 100s of methods, which isn't feasible. Moving reachability checker generation to a more central place solves that problem. The ObjectReader object seems a good place from which to get reachability checkers, because reachability checkers return information about relationships between objects. ObjectDatabases delegate many operations to ObjectReaders, and reachability bitmaps are attached to ObjectReaders. The Bitmapped and Pedestrian reachability checker objects were package private in the org.eclipse.jgit.revwalk package. This change makes them public and moves them to the org.eclipse.jgit.internal.revwalk package. Corresponding tests are also moved. Motivation: 1) Reachability checking algorithms need to scale. One of the internal Android repositories has ~2.4 million refs/changes/* references, causing bad long tail performance in reachability checks. 2) Reachability check performance is impacted by repository topography: number of refs, number of objects, amounts of related vs. unrelated history. 3) Reachability check performance is also affected by per-branch access (Gerrit branch permissions) since different users can see different branches. 4) Reachability check performance isn't affected by any state in a RevWalk or ObjectWalk. I don't yet know if a single algorithm will work for all cases in #2 and #3. We may need to evolve the ReachabilityChecker interfaces over time to solve the Gerrit branch permissions case, or use Gerrit-specific identity information to solve that in an efficient way. This change takes the existing public API and moves it to the ObjectReader/whole repository level, which is where we can do consistent customizations for #2 and #3. We intend to upstream the best of whatever works, but anticipate the need for multiple rounds of experimentation. Change-Id: I9185feff43551fb387957c436112d5250486833d Signed-off-by: Terry Parker --- org.eclipse.jgit.test/META-INF/MANIFEST.MF | 1 + .../revwalk/BitmappedObjectReachabilityTest.java | 32 ++++ .../revwalk/BitmappedReachabilityCheckerTest.java | 37 +++++ .../revwalk/ObjectReachabilityTestCase.java | 147 ++++++++++++++++++ .../revwalk/PedestrianObjectReachabilityTest.java | 26 ++++ .../revwalk/PedestrianReachabilityCheckerTest.java | 25 +++ .../revwalk/ReachabilityCheckerTestCase.java | 137 +++++++++++++++++ .../revwalk/BitmappedObjectReachabilityTest.java | 31 ---- .../revwalk/BitmappedReachabilityCheckerTest.java | 36 ----- .../jgit/revwalk/ObjectReachabilityTestCase.java | 143 ------------------ .../revwalk/PedestrianObjectReachabilityTest.java | 25 --- .../revwalk/PedestrianReachabilityCheckerTest.java | 24 --- .../jgit/revwalk/ReachabilityCheckerTestCase.java | 135 ----------------- org.eclipse.jgit/.settings/.api_filters | 16 ++ org.eclipse.jgit/META-INF/MANIFEST.MF | 3 +- .../BitmappedObjectReachabilityChecker.java | 83 ++++++++++ .../revwalk/BitmappedReachabilityChecker.java | 168 +++++++++++++++++++++ .../PedestrianObjectReachabilityChecker.java | 87 +++++++++++ .../revwalk/PedestrianReachabilityChecker.java | 70 +++++++++ .../src/org/eclipse/jgit/lib/ObjectReader.java | 57 +++++++ .../BitmappedObjectReachabilityChecker.java | 79 ---------- .../jgit/revwalk/BitmappedReachabilityChecker.java | 163 -------------------- .../src/org/eclipse/jgit/revwalk/ObjectWalk.java | 12 +- .../PedestrianObjectReachabilityChecker.java | 81 ---------- .../revwalk/PedestrianReachabilityChecker.java | 66 -------- .../src/org/eclipse/jgit/revwalk/RevWalk.java | 12 +- .../src/org/eclipse/jgit/transport/UploadPack.java | 8 +- 27 files changed, 904 insertions(+), 800 deletions(-) create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityTest.java create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityCheckerTest.java create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ObjectReachabilityTestCase.java create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityTest.java create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityCheckerTest.java create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ReachabilityCheckerTestCase.java delete mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityTest.java delete mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java delete mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ObjectReachabilityTestCase.java delete mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityTest.java delete mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java delete mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityChecker.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityChecker.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityChecker.java delete mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityChecker.java delete mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java delete mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityChecker.java delete mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF index a1239468db..0540cfb045 100644 --- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF +++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF @@ -34,6 +34,7 @@ Import-Package: com.googlecode.javaewah;version="[1.1.6,2.0.0)", org.eclipse.jgit.ignore.internal;version="[5.11.0,5.12.0)", org.eclipse.jgit.internal;version="[5.11.0,5.12.0)", org.eclipse.jgit.internal.fsck;version="[5.11.0,5.12.0)", + org.eclipse.jgit.internal.revwalk;version="[5.11.0,5.12.0)", org.eclipse.jgit.internal.storage.dfs;version="[5.11.0,5.12.0)", org.eclipse.jgit.internal.storage.file;version="[5.11.0,5.12.0)", org.eclipse.jgit.internal.storage.io;version="[5.11.0,5.12.0)", diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityTest.java new file mode 100644 index 0000000000..f2f74050b9 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityTest.java @@ -0,0 +1,32 @@ +/* + * Copyright (C) 2020, 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.internal.storage.file.GC; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; + +public class BitmappedObjectReachabilityTest + extends ObjectReachabilityTestCase { + + @Override + ObjectReachabilityChecker getChecker( + TestRepository repository) throws Exception { + // GC generates the bitmaps + GC gc = new GC(repository.getRepository()); + gc.setAuto(false); + gc.gc(); + + return new BitmappedObjectReachabilityChecker( + repository.getRevWalk().toObjectWalkWithSameObjects()); + } + +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityCheckerTest.java new file mode 100644 index 0000000000..5833c7a81b --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityCheckerTest.java @@ -0,0 +1,37 @@ +/* + * 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import static org.junit.Assert.assertNotNull; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.internal.storage.file.GC; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.revwalk.ReachabilityChecker; + +public class BitmappedReachabilityCheckerTest + extends ReachabilityCheckerTestCase { + + @Override + protected ReachabilityChecker getChecker( + TestRepository repository) throws Exception { + // GC generates the bitmaps + GC gc = new GC(repo.getRepository()); + gc.setAuto(false); + gc.gc(); + + // This is null when the test didn't create any branch + assertNotNull("Probably the test didn't define any ref", + repo.getRevWalk().getObjectReader().getBitmapIndex()); + + return new BitmappedReachabilityChecker(repository.getRevWalk()); + } + +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ObjectReachabilityTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ObjectReachabilityTestCase.java new file mode 100644 index 0000000000..37ff40bdf7 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ObjectReachabilityTestCase.java @@ -0,0 +1,147 @@ +/* + * Copyright (C) 2020, 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import java.util.Arrays; +import java.util.Optional; +import java.util.stream.Stream; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.junit.TestRepository.CommitBuilder; +import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; +import org.eclipse.jgit.revwalk.RevBlob; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevObject; +import org.junit.Before; +import org.junit.Test; + +public abstract class ObjectReachabilityTestCase + extends LocalDiskRepositoryTestCase { + + private TestRepository repo; + private AddressableRevCommit baseCommit; + private AddressableRevCommit branchACommit; + private AddressableRevCommit branchBCommit; + private AddressableRevCommit mergeCommit; + + abstract ObjectReachabilityChecker getChecker( + TestRepository repository) throws Exception; + + // Pair of commit and blob inside it + protected static class AddressableRevCommit { + RevCommit commit; + + RevBlob blob; + + AddressableRevCommit(RevCommit commit, RevBlob blob) { + this.commit = commit; + this.blob = blob; + } + } + + /** {@inheritDoc} */ + @Override + @Before + public void setUp() throws Exception { + super.setUp(); + FileRepository db = createWorkRepository(); + repo = new TestRepository<>(db); + prepareRepo(); + } + + @Test + public void blob_in_base_reachable_from_branches() throws Exception { + ObjectReachabilityChecker checker = getChecker(repo); + + RevObject baseBlob = baseCommit.blob; + assertReachable("reachable from one branch", checker.areAllReachable( + Arrays.asList(baseBlob), Stream.of(branchACommit.commit))); + assertReachable("reachable from another branch", + checker.areAllReachable( + Arrays.asList(baseBlob), + Stream.of(branchBCommit.commit))); + } + + @Test + public void blob_reachable_from_owning_commit() throws Exception { + ObjectReachabilityChecker checker = getChecker(repo); + + RevObject branchABlob = branchACommit.blob; + assertReachable("reachable from itself", + checker.areAllReachable(Arrays.asList(branchABlob), + Stream.of(branchACommit.commit))); + } + + @Test + public void blob_in_branch_reachable_from_merge() throws Exception { + ObjectReachabilityChecker checker = getChecker(repo); + + RevObject branchABlob = branchACommit.blob; + assertReachable("reachable from merge", checker.areAllReachable( + Arrays.asList(branchABlob), Stream.of(mergeCommit.commit))); + } + + @Test + public void blob_unreachable_from_earlier_commit() throws Exception { + ObjectReachabilityChecker checker = getChecker(repo); + + RevObject branchABlob = branchACommit.blob; + assertUnreachable("unreachable from earlier commit", + checker.areAllReachable(Arrays.asList(branchABlob), + Stream.of(baseCommit.commit))); + } + + @Test + public void blob_unreachable_from_parallel_branch() throws Exception { + ObjectReachabilityChecker checker = getChecker(repo); + + RevObject branchABlob = branchACommit.blob; + assertUnreachable("unreachable from another branch", + checker.areAllReachable(Arrays.asList(branchABlob), + Stream.of(branchBCommit.commit))); + } + + private void prepareRepo() throws Exception { + baseCommit = createCommit("base"); + branchACommit = createCommit("branchA", baseCommit); + branchBCommit = createCommit("branchB", baseCommit); + mergeCommit = createCommit("merge", branchACommit, branchBCommit); + + // Bitmaps are generated from references + repo.update("refs/heads/a", branchACommit.commit); + repo.update("refs/heads/b", branchBCommit.commit); + repo.update("refs/heads/merge", mergeCommit.commit); + } + + private AddressableRevCommit createCommit(String blobPath, AddressableRevCommit... parents) throws Exception { + RevBlob blob = repo.blob(blobPath + " content"); + CommitBuilder commitBuilder = repo.commit(); + for (int i = 0; i < parents.length; i++) { + commitBuilder.parent(parents[i].commit); + } + commitBuilder.add(blobPath, blob); + + RevCommit commit = commitBuilder.create(); + return new AddressableRevCommit(commit, blob); + } + + private static void assertReachable(String msg, Optional result) { + assertFalse(msg, result.isPresent()); + } + + private static void assertUnreachable(String msg, Optional result) { + assertTrue(msg, result.isPresent()); + } +} \ No newline at end of file diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityTest.java new file mode 100644 index 0000000000..f06a768340 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityTest.java @@ -0,0 +1,26 @@ +/* + * Copyright (C) 2020, 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; + +public class PedestrianObjectReachabilityTest + extends ObjectReachabilityTestCase { + + @Override + ObjectReachabilityChecker getChecker( + TestRepository repository) + throws Exception { + return new PedestrianObjectReachabilityChecker( + repository.getRevWalk().toObjectWalkWithSameObjects()); + } +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityCheckerTest.java new file mode 100644 index 0000000000..f9d4e182a4 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityCheckerTest.java @@ -0,0 +1,25 @@ +/* + * 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.revwalk.ReachabilityChecker; + +public class PedestrianReachabilityCheckerTest + extends ReachabilityCheckerTestCase { + + @Override + protected ReachabilityChecker getChecker( + TestRepository repository) { + return new PedestrianReachabilityChecker(true, repository.getRevWalk()); + } + +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ReachabilityCheckerTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ReachabilityCheckerTestCase.java new file mode 100644 index 0000000000..1ff6e7defb --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/revwalk/ReachabilityCheckerTestCase.java @@ -0,0 +1,137 @@ +/* + * 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import java.util.Arrays; +import java.util.Optional; +import java.util.stream.Stream; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.revwalk.ReachabilityChecker; +import org.eclipse.jgit.revwalk.RevCommit; +import org.junit.Before; +import org.junit.Test; + +public abstract class ReachabilityCheckerTestCase + extends LocalDiskRepositoryTestCase { + + protected abstract ReachabilityChecker getChecker( + TestRepository repository) throws Exception; + + TestRepository repo; + + /** {@inheritDoc} */ + @Override + @Before + public void setUp() throws Exception { + super.setUp(); + FileRepository db = createWorkRepository(); + repo = new TestRepository<>(db); + } + + @Test + public void reachable() throws Exception { + RevCommit a = repo.commit().create(); + RevCommit b1 = repo.commit(a); + RevCommit b2 = repo.commit(b1); + RevCommit c1 = repo.commit(a); + RevCommit c2 = repo.commit(c1); + repo.update("refs/heads/checker", b2); + + ReachabilityChecker checker = getChecker(repo); + + assertReachable("reachable from one tip", + checker.areAllReachable(Arrays.asList(a), Stream.of(c2))); + assertReachable("reachable from another tip", + checker.areAllReachable(Arrays.asList(a), Stream.of(b2))); + assertReachable("reachable from itself", + checker.areAllReachable(Arrays.asList(a), Stream.of(b2))); + } + + @Test + public void reachable_merge() throws Exception { + RevCommit a = repo.commit().create(); + RevCommit b1 = repo.commit(a); + RevCommit b2 = repo.commit(b1); + RevCommit c1 = repo.commit(a); + RevCommit c2 = repo.commit(c1); + RevCommit merge = repo.commit(c2, b2); + repo.update("refs/heads/checker", merge); + + ReachabilityChecker checker = getChecker(repo); + + assertReachable("reachable through one branch", + checker.areAllReachable(Arrays.asList(b1), + Stream.of(merge))); + assertReachable("reachable through another branch", + checker.areAllReachable(Arrays.asList(c1), + Stream.of(merge))); + assertReachable("reachable, before the branching", + checker.areAllReachable(Arrays.asList(a), + Stream.of(merge))); + } + + @Test + public void unreachable_isLaterCommit() throws Exception { + RevCommit a = repo.commit().create(); + RevCommit b1 = repo.commit(a); + RevCommit b2 = repo.commit(b1); + repo.update("refs/heads/checker", b2); + + ReachabilityChecker checker = getChecker(repo); + + assertUnreachable("unreachable from the future", + checker.areAllReachable(Arrays.asList(b2), Stream.of(b1))); + } + + @Test + public void unreachable_differentBranch() throws Exception { + RevCommit a = repo.commit().create(); + RevCommit b1 = repo.commit(a); + RevCommit b2 = repo.commit(b1); + RevCommit c1 = repo.commit(a); + repo.update("refs/heads/checker", b2); + + ReachabilityChecker checker = getChecker(repo); + + assertUnreachable("unreachable from different branch", + checker.areAllReachable(Arrays.asList(c1), Stream.of(b2))); + } + + @Test + public void reachable_longChain() throws Exception { + RevCommit root = repo.commit().create(); + RevCommit head = root; + for (int i = 0; i < 10000; i++) { + head = repo.commit(head); + } + repo.update("refs/heads/master", head); + + ReachabilityChecker checker = getChecker(repo); + + assertReachable("reachable with long chain in the middle", checker + .areAllReachable(Arrays.asList(root), Stream.of(head))); + } + + private static void assertReachable(String msg, + Optional result) { + assertFalse(msg, result.isPresent()); + } + + private static void assertUnreachable(String msg, + Optional result) { + assertTrue(msg, result.isPresent()); + } +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityTest.java deleted file mode 100644 index d2b6e89168..0000000000 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityTest.java +++ /dev/null @@ -1,31 +0,0 @@ -/* - * Copyright (C) 2020, 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import org.eclipse.jgit.internal.storage.file.FileRepository; -import org.eclipse.jgit.internal.storage.file.GC; -import org.eclipse.jgit.junit.TestRepository; - -public class BitmappedObjectReachabilityTest - extends ObjectReachabilityTestCase { - - @Override - ObjectReachabilityChecker getChecker( - TestRepository repository) throws Exception { - // GC generates the bitmaps - GC gc = new GC(repository.getRepository()); - gc.setAuto(false); - gc.gc(); - - return new BitmappedObjectReachabilityChecker( - repository.getRevWalk().toObjectWalkWithSameObjects()); - } - -} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java deleted file mode 100644 index 2cb88b979e..0000000000 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java +++ /dev/null @@ -1,36 +0,0 @@ -/* - * 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import static org.junit.Assert.assertNotNull; - -import org.eclipse.jgit.internal.storage.file.FileRepository; -import org.eclipse.jgit.internal.storage.file.GC; -import org.eclipse.jgit.junit.TestRepository; - -public class BitmappedReachabilityCheckerTest - extends ReachabilityCheckerTestCase { - - @Override - protected ReachabilityChecker getChecker( - TestRepository repository) throws Exception { - // GC generates the bitmaps - GC gc = new GC(repo.getRepository()); - gc.setAuto(false); - gc.gc(); - - // This is null when the test didn't create any branch - assertNotNull("Probably the test didn't define any ref", - repo.getRevWalk().getObjectReader().getBitmapIndex()); - - return new BitmappedReachabilityChecker(repository.getRevWalk()); - } - -} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ObjectReachabilityTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ObjectReachabilityTestCase.java deleted file mode 100644 index 267b163f43..0000000000 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ObjectReachabilityTestCase.java +++ /dev/null @@ -1,143 +0,0 @@ -/* - * Copyright (C) 2020, 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertTrue; - -import java.util.Arrays; -import java.util.Optional; -import java.util.stream.Stream; - -import org.eclipse.jgit.internal.storage.file.FileRepository; -import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase; -import org.eclipse.jgit.junit.TestRepository; -import org.eclipse.jgit.junit.TestRepository.CommitBuilder; -import org.junit.Before; -import org.junit.Test; - -public abstract class ObjectReachabilityTestCase - extends LocalDiskRepositoryTestCase { - - private TestRepository repo; - private AddressableRevCommit baseCommit; - private AddressableRevCommit branchACommit; - private AddressableRevCommit branchBCommit; - private AddressableRevCommit mergeCommit; - - abstract ObjectReachabilityChecker getChecker( - TestRepository repository) throws Exception; - - // Pair of commit and blob inside it - protected static class AddressableRevCommit { - RevCommit commit; - - RevBlob blob; - - AddressableRevCommit(RevCommit commit, RevBlob blob) { - this.commit = commit; - this.blob = blob; - } - } - - /** {@inheritDoc} */ - @Override - @Before - public void setUp() throws Exception { - super.setUp(); - FileRepository db = createWorkRepository(); - repo = new TestRepository<>(db); - prepareRepo(); - } - - @Test - public void blob_in_base_reachable_from_branches() throws Exception { - ObjectReachabilityChecker checker = getChecker(repo); - - RevObject baseBlob = baseCommit.blob; - assertReachable("reachable from one branch", checker.areAllReachable( - Arrays.asList(baseBlob), Stream.of(branchACommit.commit))); - assertReachable("reachable from another branch", - checker.areAllReachable( - Arrays.asList(baseBlob), - Stream.of(branchBCommit.commit))); - } - - @Test - public void blob_reachable_from_owning_commit() throws Exception { - ObjectReachabilityChecker checker = getChecker(repo); - - RevObject branchABlob = branchACommit.blob; - assertReachable("reachable from itself", - checker.areAllReachable(Arrays.asList(branchABlob), - Stream.of(branchACommit.commit))); - } - - @Test - public void blob_in_branch_reachable_from_merge() throws Exception { - ObjectReachabilityChecker checker = getChecker(repo); - - RevObject branchABlob = branchACommit.blob; - assertReachable("reachable from merge", checker.areAllReachable( - Arrays.asList(branchABlob), Stream.of(mergeCommit.commit))); - } - - @Test - public void blob_unreachable_from_earlier_commit() throws Exception { - ObjectReachabilityChecker checker = getChecker(repo); - - RevObject branchABlob = branchACommit.blob; - assertUnreachable("unreachable from earlier commit", - checker.areAllReachable(Arrays.asList(branchABlob), - Stream.of(baseCommit.commit))); - } - - @Test - public void blob_unreachable_from_parallel_branch() throws Exception { - ObjectReachabilityChecker checker = getChecker(repo); - - RevObject branchABlob = branchACommit.blob; - assertUnreachable("unreachable from another branch", - checker.areAllReachable(Arrays.asList(branchABlob), - Stream.of(branchBCommit.commit))); - } - - private void prepareRepo() throws Exception { - baseCommit = createCommit("base"); - branchACommit = createCommit("branchA", baseCommit); - branchBCommit = createCommit("branchB", baseCommit); - mergeCommit = createCommit("merge", branchACommit, branchBCommit); - - // Bitmaps are generated from references - repo.update("refs/heads/a", branchACommit.commit); - repo.update("refs/heads/b", branchBCommit.commit); - repo.update("refs/heads/merge", mergeCommit.commit); - } - - private AddressableRevCommit createCommit(String blobPath, AddressableRevCommit... parents) throws Exception { - RevBlob blob = repo.blob(blobPath + " content"); - CommitBuilder commitBuilder = repo.commit(); - for (int i = 0; i < parents.length; i++) { - commitBuilder.parent(parents[i].commit); - } - commitBuilder.add(blobPath, blob); - - RevCommit commit = commitBuilder.create(); - return new AddressableRevCommit(commit, blob); - } - - private static void assertReachable(String msg, Optional result) { - assertFalse(msg, result.isPresent()); - } - - private static void assertUnreachable(String msg, Optional result) { - assertTrue(msg, result.isPresent()); - } -} \ No newline at end of file diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityTest.java deleted file mode 100644 index b1c9556df8..0000000000 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityTest.java +++ /dev/null @@ -1,25 +0,0 @@ -/* - * Copyright (C) 2020, 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import org.eclipse.jgit.internal.storage.file.FileRepository; -import org.eclipse.jgit.junit.TestRepository; - -public class PedestrianObjectReachabilityTest - extends ObjectReachabilityTestCase { - - @Override - ObjectReachabilityChecker getChecker( - TestRepository repository) - throws Exception { - return new PedestrianObjectReachabilityChecker( - repository.getRevWalk().toObjectWalkWithSameObjects()); - } -} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java deleted file mode 100644 index 3029e056eb..0000000000 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java +++ /dev/null @@ -1,24 +0,0 @@ -/* - * 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import org.eclipse.jgit.internal.storage.file.FileRepository; -import org.eclipse.jgit.junit.TestRepository; - -public class PedestrianReachabilityCheckerTest - extends ReachabilityCheckerTestCase { - - @Override - protected ReachabilityChecker getChecker( - TestRepository repository) { - return new PedestrianReachabilityChecker(true, repository.getRevWalk()); - } - -} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java deleted file mode 100644 index 4695eaa695..0000000000 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java +++ /dev/null @@ -1,135 +0,0 @@ -/* - * 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertTrue; - -import java.util.Arrays; -import java.util.Optional; -import java.util.stream.Stream; - -import org.eclipse.jgit.internal.storage.file.FileRepository; -import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase; -import org.eclipse.jgit.junit.TestRepository; -import org.junit.Before; -import org.junit.Test; - -public abstract class ReachabilityCheckerTestCase - extends LocalDiskRepositoryTestCase { - - protected abstract ReachabilityChecker getChecker( - TestRepository repository) throws Exception; - - TestRepository repo; - - /** {@inheritDoc} */ - @Override - @Before - public void setUp() throws Exception { - super.setUp(); - FileRepository db = createWorkRepository(); - repo = new TestRepository<>(db); - } - - @Test - public void reachable() throws Exception { - RevCommit a = repo.commit().create(); - RevCommit b1 = repo.commit(a); - RevCommit b2 = repo.commit(b1); - RevCommit c1 = repo.commit(a); - RevCommit c2 = repo.commit(c1); - repo.update("refs/heads/checker", b2); - - ReachabilityChecker checker = getChecker(repo); - - assertReachable("reachable from one tip", - checker.areAllReachable(Arrays.asList(a), Stream.of(c2))); - assertReachable("reachable from another tip", - checker.areAllReachable(Arrays.asList(a), Stream.of(b2))); - assertReachable("reachable from itself", - checker.areAllReachable(Arrays.asList(a), Stream.of(b2))); - } - - @Test - public void reachable_merge() throws Exception { - RevCommit a = repo.commit().create(); - RevCommit b1 = repo.commit(a); - RevCommit b2 = repo.commit(b1); - RevCommit c1 = repo.commit(a); - RevCommit c2 = repo.commit(c1); - RevCommit merge = repo.commit(c2, b2); - repo.update("refs/heads/checker", merge); - - ReachabilityChecker checker = getChecker(repo); - - assertReachable("reachable through one branch", - checker.areAllReachable(Arrays.asList(b1), - Stream.of(merge))); - assertReachable("reachable through another branch", - checker.areAllReachable(Arrays.asList(c1), - Stream.of(merge))); - assertReachable("reachable, before the branching", - checker.areAllReachable(Arrays.asList(a), - Stream.of(merge))); - } - - @Test - public void unreachable_isLaterCommit() throws Exception { - RevCommit a = repo.commit().create(); - RevCommit b1 = repo.commit(a); - RevCommit b2 = repo.commit(b1); - repo.update("refs/heads/checker", b2); - - ReachabilityChecker checker = getChecker(repo); - - assertUnreachable("unreachable from the future", - checker.areAllReachable(Arrays.asList(b2), Stream.of(b1))); - } - - @Test - public void unreachable_differentBranch() throws Exception { - RevCommit a = repo.commit().create(); - RevCommit b1 = repo.commit(a); - RevCommit b2 = repo.commit(b1); - RevCommit c1 = repo.commit(a); - repo.update("refs/heads/checker", b2); - - ReachabilityChecker checker = getChecker(repo); - - assertUnreachable("unreachable from different branch", - checker.areAllReachable(Arrays.asList(c1), Stream.of(b2))); - } - - @Test - public void reachable_longChain() throws Exception { - RevCommit root = repo.commit().create(); - RevCommit head = root; - for (int i = 0; i < 10000; i++) { - head = repo.commit(head); - } - repo.update("refs/heads/master", head); - - ReachabilityChecker checker = getChecker(repo); - - assertReachable("reachable with long chain in the middle", checker - .areAllReachable(Arrays.asList(root), Stream.of(head))); - } - - private static void assertReachable(String msg, - Optional result) { - assertFalse(msg, result.isPresent()); - } - - private static void assertUnreachable(String msg, - Optional result) { - assertTrue(msg, result.isPresent()); - } -} diff --git a/org.eclipse.jgit/.settings/.api_filters b/org.eclipse.jgit/.settings/.api_filters index 8f1433cf55..b74e703a0c 100644 --- a/org.eclipse.jgit/.settings/.api_filters +++ b/org.eclipse.jgit/.settings/.api_filters @@ -8,4 +8,20 @@ + + + + + + + + + + + + + + + + diff --git a/org.eclipse.jgit/META-INF/MANIFEST.MF b/org.eclipse.jgit/META-INF/MANIFEST.MF index 9dc26ecb49..47b030ca04 100644 --- a/org.eclipse.jgit/META-INF/MANIFEST.MF +++ b/org.eclipse.jgit/META-INF/MANIFEST.MF @@ -72,7 +72,8 @@ Export-Package: org.eclipse.jgit.annotations;version="5.11.0", org.eclipse.jgit.http.test", org.eclipse.jgit.internal.fsck;version="5.11.0"; x-friends:="org.eclipse.jgit.test", - org.eclipse.jgit.internal.revwalk;version="5.11.0";x-internal:=true, + org.eclipse.jgit.internal.revwalk;version="5.11.0"; + x-friends:="org.eclipse.jgit.test", org.eclipse.jgit.internal.storage.dfs;version="5.11.0"; x-friends:="org.eclipse.jgit.test, org.eclipse.jgit.http.server, diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityChecker.java new file mode 100644 index 0000000000..d8056490aa --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedObjectReachabilityChecker.java @@ -0,0 +1,83 @@ +/* + * Copyright (C) 2020, 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.Optional; +import java.util.stream.Stream; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.revwalk.BitmapWalker; +import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; +import org.eclipse.jgit.revwalk.ObjectWalk; +import org.eclipse.jgit.revwalk.RevObject; + +/** + * Checks if all objects are reachable from certain starting points using + * bitmaps. + */ +public class BitmappedObjectReachabilityChecker + implements ObjectReachabilityChecker { + + private final ObjectWalk walk; + + /** + * New instance of the reachability checker using a existing walk. + * + * @param walk + * ObjectWalk instance to reuse. Caller retains ownership. + */ + public BitmappedObjectReachabilityChecker(ObjectWalk walk) { + this.walk = walk; + } + + /** + * {@inheritDoc} + * + * This implementation tries to shortcut the check adding starters + * incrementally. Ordering the starters by relevance can improve performance + * in the average case. + */ + @Override + public Optional areAllReachable(Collection targets, + Stream starters) throws IOException { + + try { + List remainingTargets = new ArrayList<>(targets); + BitmapWalker bitmapWalker = new BitmapWalker(walk, + walk.getObjectReader().getBitmapIndex(), null); + + Iterator starterIt = starters.iterator(); + BitmapBuilder seen = null; + while (starterIt.hasNext()) { + List asList = Arrays.asList(starterIt.next()); + BitmapBuilder visited = bitmapWalker.findObjects(asList, seen, + true); + seen = seen == null ? visited : seen.or(visited); + + remainingTargets.removeIf(seen::contains); + if (remainingTargets.isEmpty()) { + return Optional.empty(); + } + } + + return Optional.of(remainingTargets.get(0)); + } catch (MissingObjectException | IncorrectObjectTypeException e) { + throw new IllegalStateException(e); + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityChecker.java new file mode 100644 index 0000000000..37721ad1ea --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/BitmappedReachabilityChecker.java @@ -0,0 +1,168 @@ +/* + * 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.Optional; +import java.util.stream.Stream; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.lib.BitmapIndex; +import org.eclipse.jgit.lib.BitmapIndex.Bitmap; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.revwalk.ReachabilityChecker; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevFlag; +import org.eclipse.jgit.revwalk.RevSort; +import org.eclipse.jgit.revwalk.RevWalk; +import org.eclipse.jgit.revwalk.filter.RevFilter; + +/** + * Checks the reachability using bitmaps. + */ +public class BitmappedReachabilityChecker implements ReachabilityChecker { + + private final RevWalk walk; + + /** + * @param walk + * walk on the repository to get or create the bitmaps for the + * commits. It must have bitmaps. + * @throws AssertionError + * runtime exception if walk is over a repository without + * bitmaps + * @throws IOException + * if the index or the object reader cannot be opened. + */ + public BitmappedReachabilityChecker(RevWalk walk) + throws IOException { + this.walk = walk; + if (walk.getObjectReader().getBitmapIndex() == null) { + throw new AssertionError( + "Trying to use bitmapped reachability check " //$NON-NLS-1$ + + "on a repository without bitmaps"); //$NON-NLS-1$ + } + } + + /** + * Check all targets are reachable from the starters. + *

+ * In this implementation, it is recommended to put the most popular + * starters (e.g. refs/heads tips) at the beginning. + */ + @Override + public Optional areAllReachable(Collection targets, + Stream starters) throws MissingObjectException, + IncorrectObjectTypeException, IOException { + + List remainingTargets = new ArrayList<>(targets); + + walk.reset(); + walk.sort(RevSort.TOPO); + + // Filter emits only commits that are unreachable from previously + // visited commits. Internally it keeps a bitmap of everything + // reachable so far, which we use to discard reachable targets. + BitmapIndex repoBitmaps = walk.getObjectReader().getBitmapIndex(); + ReachedFilter reachedFilter = new ReachedFilter(repoBitmaps); + walk.setRevFilter(reachedFilter); + + Iterator startersIter = starters.iterator(); + while (startersIter.hasNext()) { + walk.markStart(startersIter.next()); + while (walk.next() != null) { + remainingTargets.removeIf(reachedFilter::isReachable); + + if (remainingTargets.isEmpty()) { + return Optional.empty(); + } + } + walk.reset(); + } + + return Optional.of(remainingTargets.get(0)); + } + + /** + * This filter emits commits that were not bitmap-reachable from anything + * visited before. Or in other words, commits that add something (themselves + * or their bitmap) to the "reached" bitmap. + * + * Current progress can be queried via {@link #isReachable(RevCommit)}. + */ + private static class ReachedFilter extends RevFilter { + + private final BitmapIndex repoBitmaps; + private final BitmapBuilder reached; + + /** + * Create a filter that emits only previously unreachable commits. + * + * @param repoBitmaps + * bitmap index of the repo + */ + public ReachedFilter(BitmapIndex repoBitmaps) { + this.repoBitmaps = repoBitmaps; + this.reached = repoBitmaps.newBitmapBuilder(); + } + + /** {@inheritDoc} */ + @Override + public final boolean include(RevWalk walker, RevCommit cmit) { + Bitmap commitBitmap; + + if (reached.contains(cmit)) { + // already seen or included + dontFollow(cmit); + return false; + } + + if ((commitBitmap = repoBitmaps.getBitmap(cmit)) != null) { + reached.or(commitBitmap); + // Emit the commit because there are new contents in the bitmap + // but don't follow parents (they are already in the bitmap) + dontFollow(cmit); + return true; + } + + // No bitmaps, keep going + reached.addObject(cmit, Constants.OBJ_COMMIT); + return true; + } + + private static final void dontFollow(RevCommit cmit) { + for (RevCommit p : cmit.getParents()) { + p.add(RevFlag.SEEN); + } + } + + /** {@inheritDoc} */ + @Override + public final RevFilter clone() { + throw new UnsupportedOperationException(); + } + + /** {@inheritDoc} */ + @Override + public final boolean requiresCommitBody() { + return false; + } + + boolean isReachable(RevCommit commit) { + return reached.contains(commit); + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java new file mode 100644 index 0000000000..1d1f5fddaf --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java @@ -0,0 +1,87 @@ +/* + * Copyright (C) 2020, 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import java.io.IOException; +import java.io.InvalidObjectException; +import java.util.Collection; +import java.util.Iterator; +import java.util.Optional; +import java.util.stream.Stream; + +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; +import org.eclipse.jgit.revwalk.ObjectWalk; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevObject; +import org.eclipse.jgit.revwalk.RevSort; + +/** + * Checks if all objects are reachable from certain starting points doing a + * walk. + */ +public class PedestrianObjectReachabilityChecker + implements ObjectReachabilityChecker { + private final ObjectWalk walk; + + /** + * New instance of the reachability checker using a existing walk. + * + * @param walk + * ObjectWalk instance to reuse. Caller retains ownership. + */ + public PedestrianObjectReachabilityChecker(ObjectWalk walk) { + this.walk = walk; + } + + /** + * {@inheritDoc} + */ + @Override + public Optional areAllReachable(Collection targets, + Stream starters) throws IOException { + try { + walk.reset(); + walk.sort(RevSort.TOPO); + for (RevObject target : targets) { + walk.markStart(target); + } + + Iterator iterator = starters.iterator(); + while (iterator.hasNext()) { + RevObject o = iterator.next(); + walk.markUninteresting(o); + + RevObject peeled = walk.peel(o); + if (peeled instanceof RevCommit) { + // By default, for performance reasons, ObjectWalk does not + // mark + // a tree as uninteresting when we mark a commit. Mark it + // ourselves so that we can determine reachability exactly. + walk.markUninteresting(((RevCommit) peeled).getTree()); + } + } + + RevCommit commit = walk.next(); + if (commit != null) { + return Optional.of(commit); + } + + RevObject object = walk.nextObject(); + if (object != null) { + return Optional.of(object); + } + + return Optional.empty(); + } catch (MissingObjectException | InvalidObjectException e) { + throw new IllegalStateException(e); + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityChecker.java new file mode 100644 index 0000000000..a03306b6ee --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianReachabilityChecker.java @@ -0,0 +1,70 @@ +/* + * 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 + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.revwalk; + +import java.io.IOException; +import java.util.Collection; +import java.util.Iterator; +import java.util.Optional; +import java.util.stream.Stream; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.revwalk.ReachabilityChecker; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevSort; +import org.eclipse.jgit.revwalk.RevWalk; + +/** + * Checks the reachability walking the graph from the starters towards the + * target. + */ +public class PedestrianReachabilityChecker implements ReachabilityChecker { + + private final boolean topoSort; + + private final RevWalk walk; + + /** + * New instance of the reachability checker using a existing walk. + * + * @param topoSort + * walk commits in topological order + * @param walk + * RevWalk instance to reuse. Caller retains ownership. + */ + public PedestrianReachabilityChecker(boolean topoSort, + RevWalk walk) { + this.topoSort = topoSort; + this.walk = walk; + } + + @Override + public Optional areAllReachable(Collection targets, + Stream starters) + throws MissingObjectException, IncorrectObjectTypeException, + IOException { + walk.reset(); + if (topoSort) { + walk.sort(RevSort.TOPO); + } + + for (RevCommit target: targets) { + walk.markStart(target); + } + + Iterator iterator = starters.iterator(); + while (iterator.hasNext()) { + walk.markUninteresting(iterator.next()); + } + + return Optional.ofNullable(walk.next()); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java index 6bb6ae590a..718ed89142 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java @@ -17,9 +17,18 @@ import java.util.Iterator; import java.util.List; import java.util.Set; +import org.eclipse.jgit.annotations.NonNull; import org.eclipse.jgit.annotations.Nullable; import org.eclipse.jgit.errors.IncorrectObjectTypeException; import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.internal.revwalk.BitmappedObjectReachabilityChecker; +import org.eclipse.jgit.internal.revwalk.BitmappedReachabilityChecker; +import org.eclipse.jgit.internal.revwalk.PedestrianObjectReachabilityChecker; +import org.eclipse.jgit.internal.revwalk.PedestrianReachabilityChecker; +import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; +import org.eclipse.jgit.revwalk.ObjectWalk; +import org.eclipse.jgit.revwalk.ReachabilityChecker; +import org.eclipse.jgit.revwalk.RevWalk; /** * Reads an {@link org.eclipse.jgit.lib.ObjectDatabase} for a single thread. @@ -407,6 +416,54 @@ public abstract class ObjectReader implements AutoCloseable { return null; } + /** + * Create a reachability checker that will use bitmaps if possible. + * + * @param rw + * revwalk for use by the reachability checker + * @return the most efficient reachability checker for this repository. + * @throws IOException + * if it cannot open any of the underlying indices. + * + * @since 5.11 + */ + @NonNull + public ReachabilityChecker createReachabilityChecker(RevWalk rw) + throws IOException { + if (getBitmapIndex() != null) { + return new BitmappedReachabilityChecker(rw); + } + + return new PedestrianReachabilityChecker(true, rw); + } + + /** + * Create an object reachability checker that will use bitmaps if possible. + * + * This reachability checker accepts any object as target. For checks + * exclusively between commits, use + * {@link #createReachabilityChecker(RevWalk)}. + * + * @param ow + * objectwalk for use by the reachability checker + * @return the most efficient object reachability checker for this + * repository. + * + * @throws IOException + * if it cannot open any of the underlying indices. + * + * @since 5.11 + */ + @NonNull + public ObjectReachabilityChecker createObjectReachabilityChecker( + ObjectWalk ow) throws IOException { + if (getBitmapIndex() != null) { + return new BitmappedObjectReachabilityChecker(ow); + } + + return new PedestrianObjectReachabilityChecker(ow); + } + /** * Get the {@link org.eclipse.jgit.lib.ObjectInserter} from which this * reader was created using {@code inserter.newReader()} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityChecker.java deleted file mode 100644 index 89aef7dc41..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedObjectReachabilityChecker.java +++ /dev/null @@ -1,79 +0,0 @@ -/* - * Copyright (C) 2020, 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import java.io.IOException; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collection; -import java.util.Iterator; -import java.util.List; -import java.util.Optional; -import java.util.stream.Stream; - -import org.eclipse.jgit.errors.IncorrectObjectTypeException; -import org.eclipse.jgit.errors.MissingObjectException; -import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; - -/** - * Checks if all objects are reachable from certain starting points using - * bitmaps. - */ -class BitmappedObjectReachabilityChecker - implements ObjectReachabilityChecker { - - private final ObjectWalk walk; - - /** - * New instance of the reachability checker using a existing walk. - * - * @param walk - * ObjectWalk instance to reuse. Caller retains ownership. - */ - public BitmappedObjectReachabilityChecker(ObjectWalk walk) { - this.walk = walk; - } - - /** - * {@inheritDoc} - * - * This implementation tries to shortcut the check adding starters - * incrementally. Ordering the starters by relevance can improve performance - * in the average case. - */ - @Override - public Optional areAllReachable(Collection targets, - Stream starters) throws IOException { - - try { - List remainingTargets = new ArrayList<>(targets); - BitmapWalker bitmapWalker = new BitmapWalker(walk, - walk.getObjectReader().getBitmapIndex(), null); - - Iterator starterIt = starters.iterator(); - BitmapBuilder seen = null; - while (starterIt.hasNext()) { - List asList = Arrays.asList(starterIt.next()); - BitmapBuilder visited = bitmapWalker.findObjects(asList, seen, - true); - seen = seen == null ? visited : seen.or(visited); - - remainingTargets.removeIf(seen::contains); - if (remainingTargets.isEmpty()) { - return Optional.empty(); - } - } - - return Optional.of(remainingTargets.get(0)); - } catch (MissingObjectException | IncorrectObjectTypeException e) { - throw new IllegalStateException(e); - } - } -} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java deleted file mode 100644 index 0d9c4593bf..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java +++ /dev/null @@ -1,163 +0,0 @@ -/* - * 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import java.io.IOException; -import java.util.ArrayList; -import java.util.Collection; -import java.util.Iterator; -import java.util.List; -import java.util.Optional; -import java.util.stream.Stream; - -import org.eclipse.jgit.errors.IncorrectObjectTypeException; -import org.eclipse.jgit.errors.MissingObjectException; -import org.eclipse.jgit.lib.BitmapIndex; -import org.eclipse.jgit.lib.BitmapIndex.Bitmap; -import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; -import org.eclipse.jgit.lib.Constants; -import org.eclipse.jgit.revwalk.filter.RevFilter; - -/** - * Checks the reachability using bitmaps. - */ -class BitmappedReachabilityChecker implements ReachabilityChecker { - - private final RevWalk walk; - - /** - * @param walk - * walk on the repository to get or create the bitmaps for the - * commits. It must have bitmaps. - * @throws AssertionError - * runtime exception if walk is over a repository without - * bitmaps - * @throws IOException - * if the index or the object reader cannot be opened. - */ - BitmappedReachabilityChecker(RevWalk walk) - throws IOException { - this.walk = walk; - if (walk.getObjectReader().getBitmapIndex() == null) { - throw new AssertionError( - "Trying to use bitmapped reachability check " //$NON-NLS-1$ - + "on a repository without bitmaps"); //$NON-NLS-1$ - } - } - - /** - * Check all targets are reachable from the starters. - *

- * In this implementation, it is recommended to put the most popular - * starters (e.g. refs/heads tips) at the beginning. - */ - @Override - public Optional areAllReachable(Collection targets, - Stream starters) throws MissingObjectException, - IncorrectObjectTypeException, IOException { - - List remainingTargets = new ArrayList<>(targets); - - walk.reset(); - walk.sort(RevSort.TOPO); - - // Filter emits only commits that are unreachable from previously - // visited commits. Internally it keeps a bitmap of everything - // reachable so far, which we use to discard reachable targets. - BitmapIndex repoBitmaps = walk.getObjectReader().getBitmapIndex(); - ReachedFilter reachedFilter = new ReachedFilter(repoBitmaps); - walk.setRevFilter(reachedFilter); - - Iterator startersIter = starters.iterator(); - while (startersIter.hasNext()) { - walk.markStart(startersIter.next()); - while (walk.next() != null) { - remainingTargets.removeIf(reachedFilter::isReachable); - - if (remainingTargets.isEmpty()) { - return Optional.empty(); - } - } - walk.reset(); - } - - return Optional.of(remainingTargets.get(0)); - } - - /** - * This filter emits commits that were not bitmap-reachable from anything - * visited before. Or in other words, commits that add something (themselves - * or their bitmap) to the "reached" bitmap. - * - * Current progress can be queried via {@link #isReachable(RevCommit)}. - */ - private static class ReachedFilter extends RevFilter { - - private final BitmapIndex repoBitmaps; - private final BitmapBuilder reached; - - /** - * Create a filter that emits only previously unreachable commits. - * - * @param repoBitmaps - * bitmap index of the repo - */ - public ReachedFilter(BitmapIndex repoBitmaps) { - this.repoBitmaps = repoBitmaps; - this.reached = repoBitmaps.newBitmapBuilder(); - } - - /** {@inheritDoc} */ - @Override - public final boolean include(RevWalk walker, RevCommit cmit) { - Bitmap commitBitmap; - - if (reached.contains(cmit)) { - // already seen or included - dontFollow(cmit); - return false; - } - - if ((commitBitmap = repoBitmaps.getBitmap(cmit)) != null) { - reached.or(commitBitmap); - // Emit the commit because there are new contents in the bitmap - // but don't follow parents (they are already in the bitmap) - dontFollow(cmit); - return true; - } - - // No bitmaps, keep going - reached.addObject(cmit, Constants.OBJ_COMMIT); - return true; - } - - private static final void dontFollow(RevCommit cmit) { - for (RevCommit p : cmit.getParents()) { - p.add(RevFlag.SEEN); - } - } - - /** {@inheritDoc} */ - @Override - public final RevFilter clone() { - throw new UnsupportedOperationException(); - } - - /** {@inheritDoc} */ - @Override - public final boolean requiresCommitBody() { - return false; - } - - boolean isReachable(RevCommit commit) { - return reached.contains(commit); - } - } -} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java index 4c7a6f556e..e6f9580bf7 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java @@ -172,14 +172,14 @@ public class ObjectWalk extends RevWalk { * when the index fails to load. * * @since 5.8 + * @deprecated use + * {@code ObjectReader#createObjectReachabilityChecker(ObjectWalk)} + * instead. */ - public ObjectReachabilityChecker createObjectReachabilityChecker() + @Deprecated + public final ObjectReachabilityChecker createObjectReachabilityChecker() throws IOException { - if (reader.getBitmapIndex() != null) { - return new BitmappedObjectReachabilityChecker(this); - } - - return new PedestrianObjectReachabilityChecker(this); + return reader.createObjectReachabilityChecker(this); } /** diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityChecker.java deleted file mode 100644 index df5d68a66e..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianObjectReachabilityChecker.java +++ /dev/null @@ -1,81 +0,0 @@ -/* - * Copyright (C) 2020, 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import java.io.IOException; -import java.io.InvalidObjectException; -import java.util.Collection; -import java.util.Iterator; -import java.util.Optional; -import java.util.stream.Stream; - -import org.eclipse.jgit.errors.MissingObjectException; - -/** - * Checks if all objects are reachable from certain starting points doing a - * walk. - */ -class PedestrianObjectReachabilityChecker implements ObjectReachabilityChecker { - private final ObjectWalk walk; - - /** - * New instance of the reachability checker using a existing walk. - * - * @param walk - * ObjectWalk instance to reuse. Caller retains ownership. - */ - PedestrianObjectReachabilityChecker(ObjectWalk walk) { - this.walk = walk; - } - - /** - * {@inheritDoc} - */ - @Override - public Optional areAllReachable(Collection targets, - Stream starters) throws IOException { - try { - walk.reset(); - walk.sort(RevSort.TOPO); - for (RevObject target : targets) { - walk.markStart(target); - } - - Iterator iterator = starters.iterator(); - while (iterator.hasNext()) { - RevObject o = iterator.next(); - walk.markUninteresting(o); - - RevObject peeled = walk.peel(o); - if (peeled instanceof RevCommit) { - // By default, for performance reasons, ObjectWalk does not - // mark - // a tree as uninteresting when we mark a commit. Mark it - // ourselves so that we can determine reachability exactly. - walk.markUninteresting(((RevCommit) peeled).getTree()); - } - } - - RevCommit commit = walk.next(); - if (commit != null) { - return Optional.of(commit); - } - - RevObject object = walk.nextObject(); - if (object != null) { - return Optional.of(object); - } - - return Optional.empty(); - } catch (MissingObjectException | InvalidObjectException e) { - throw new IllegalStateException(e); - } - } -} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java deleted file mode 100644 index 5dc03776c2..0000000000 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java +++ /dev/null @@ -1,66 +0,0 @@ -/* - * 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 - * https://www.eclipse.org/org/documents/edl-v10.php. - * - * SPDX-License-Identifier: BSD-3-Clause - */ -package org.eclipse.jgit.revwalk; - -import java.io.IOException; -import java.util.Collection; -import java.util.Iterator; -import java.util.Optional; -import java.util.stream.Stream; - -import org.eclipse.jgit.errors.IncorrectObjectTypeException; -import org.eclipse.jgit.errors.MissingObjectException; - -/** - * Checks the reachability walking the graph from the starters towards the - * target. - */ -class PedestrianReachabilityChecker implements ReachabilityChecker { - - private final boolean topoSort; - - private final RevWalk walk; - - /** - * New instance of the reachability checker using a existing walk. - * - * @param topoSort - * walk commits in topological order - * @param walk - * RevWalk instance to reuse. Caller retains ownership. - */ - public PedestrianReachabilityChecker(boolean topoSort, - RevWalk walk) { - this.topoSort = topoSort; - this.walk = walk; - } - - @Override - public Optional areAllReachable(Collection targets, - Stream starters) - throws MissingObjectException, IncorrectObjectTypeException, - IOException { - walk.reset(); - if (topoSort) { - walk.sort(RevSort.TOPO); - } - - for (RevCommit target: targets) { - walk.markStart(target); - } - - Iterator iterator = starters.iterator(); - while (iterator.hasNext()) { - walk.markUninteresting(iterator.next()); - } - - return Optional.ofNullable(walk.next()); - } -} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java index 6b62fcdf6d..631d861c0d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java @@ -236,13 +236,13 @@ public class RevWalk implements Iterable, AutoCloseable { * if it cannot open any of the underlying indices. * * @since 5.4 + * @deprecated use {@code ObjectReader#createReachabilityChecker(RevWalk)} + * instead. */ - public ReachabilityChecker createReachabilityChecker() throws IOException { - if (reader.getBitmapIndex() != null) { - return new BitmappedReachabilityChecker(this); - } - - return new PedestrianReachabilityChecker(true, this); + @Deprecated + public final ReachabilityChecker createReachabilityChecker() + throws IOException { + return reader.createReachabilityChecker(this); } /** diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java index e0b86f5c11..7f1ddaab2e 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java @@ -1959,8 +1959,8 @@ public class UploadPack { .map(objId -> objectIdToRevObject(objWalk, objId)) .filter(Objects::nonNull); // Ignore missing tips - ObjectReachabilityChecker reachabilityChecker = objWalk - .createObjectReachabilityChecker(); + ObjectReachabilityChecker reachabilityChecker = reader + .createObjectReachabilityChecker(objWalk); Optional unreachable = reachabilityChecker .areAllReachable(wantsAsObjs, startersAsObjs); if (unreachable.isPresent()) { @@ -1971,8 +1971,8 @@ public class UploadPack { } // All wants are commits, we can use ReachabilityChecker - ReachabilityChecker reachabilityChecker = walk - .createReachabilityChecker(); + ReachabilityChecker reachabilityChecker = reader + .createReachabilityChecker(walk); Stream reachableCommits = importantRefsFirst(visibleRefs) .map(UploadPack::refToObjectId) -- cgit v1.2.3