From 4e196faa1bbe8b4c061662d70479d2b189b4082f Mon Sep 17 00:00:00 2001 From: Ivan Frade Date: Mon, 22 Apr 2019 11:37:43 -0700 Subject: ReachabilityChecker: Default implementation with a RevWalk It is common to check if a certain commit is reachable from some starting points. For example gitiles does it to check if a commit is visible to a user based on its permissions. Offer this functionality in JGit. Split the interface as the next commit will introduce an implementation using bitmap indices. Change-Id: I0933b305c8d734f7a64502910ff4d9ef4fc92ae1 Signed-off-by: Ivan Frade --- .../revwalk/PedestrianReachabilityCheckerTest.java | 57 +++++++ .../jgit/revwalk/ReachabilityCheckerTestCase.java | 168 +++++++++++++++++++++ .../revwalk/PedestrianReachabilityChecker.java | 98 ++++++++++++ .../eclipse/jgit/revwalk/ReachabilityChecker.java | 90 +++++++++++ 4 files changed, 413 insertions(+) create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java 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 new file mode 100644 index 0000000000..8d3e78c1fe --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java @@ -0,0 +1,57 @@ +/* + * Copyright (C) 2019, Google LLC. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.eclipse.jgit.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 new file mode 100644 index 0000000000..dd73e35727 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java @@ -0,0 +1,168 @@ +/* + * Copyright (C) 2019, Google LLC. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.eclipse.jgit.revwalk; + +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import java.util.Arrays; +import java.util.Optional; + +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), Arrays.asList(c2))); + assertReachable("reachable from another tip", + checker.areAllReachable(Arrays.asList(a), Arrays.asList(b2))); + assertReachable("reachable from itself", + checker.areAllReachable(Arrays.asList(a), Arrays.asList(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), + Arrays.asList(merge))); + assertReachable("reachable through another branch", + checker.areAllReachable(Arrays.asList(c1), + Arrays.asList(merge))); + assertReachable("reachable, before the branching", + checker.areAllReachable(Arrays.asList(a), + Arrays.asList(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), Arrays.asList(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), Arrays.asList(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), Arrays.asList(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/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java new file mode 100644 index 0000000000..2704b69cb0 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java @@ -0,0 +1,98 @@ +/* + * Copyright (C) 2019, Google LLC. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.eclipse.jgit.revwalk; + +import java.io.IOException; +import java.util.Collection; +import java.util.Optional; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; + +/** + * Checks the reachability walking the graph from the starters towards the + * target. + * + * @since 5.5 + */ +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, + Collection starters) + throws MissingObjectException, IncorrectObjectTypeException, + IOException { + walk.reset(); + if (topoSort) { + walk.sort(RevSort.TOPO); + } + + for (RevCommit target: targets) { + walk.markStart(target); + } + + for (RevCommit starter : starters) { + walk.markUninteresting(starter); + } + + return Optional.ofNullable(walk.next()); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java new file mode 100644 index 0000000000..cf5f4a28cf --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java @@ -0,0 +1,90 @@ +/* + * Copyright (C) 2019, Google LLC. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.eclipse.jgit.revwalk; + +import java.io.IOException; +import java.util.Collection; +import java.util.Optional; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; + +/** + * Check if a commit is reachable from a collection of starting commits. + *

+ * Note that this checks the reachability of commits (and tags). Trees, blobs or + * any other object will cause IncorrectObjectTypeException exceptions. + * + * @since 5.5 + */ +public interface ReachabilityChecker { + + /** + * Check if all targets are reachable from the {@code starter} commits. + *

+ * Caller should parse the objectIds (preferably with + * {@code walk.parseCommit()} and handle missing/incorrect type objects + * before calling this method. + * + * @param targets + * commits to reach. + * @param starters + * known starting points. + * @return An unreachable target if at least one of the targets is + * unreachable. An empty optional if all targets are reachable from + * the starters. + * + * @throws MissingObjectException + * if any of the incoming objects doesn't exist in the + * repository. + * @throws IncorrectObjectTypeException + * if any of the incoming objects is not a commit or a tag. + * @throws IOException + * if any of the underlying indexes or readers can not be + * opened. + */ + Optional areAllReachable(Collection targets, + Collection starters) + throws MissingObjectException, IncorrectObjectTypeException, + IOException; +} -- cgit v1.2.3 From b6da4b34cccc39a253d34e159a13cc2fd79a46bf Mon Sep 17 00:00:00 2001 From: Ivan Frade Date: Mon, 6 May 2019 20:39:18 -0700 Subject: BitmapCalculator: Get the reachability bitmap of a commit To make reachability checks with bitmaps, we need to get the reachability bitmap of a commit, which is not always precalculated. There is already a class returning such bitmap (BitmapWalker) but it does too much unnecessary work: it calculates ALL reachable objects from a commit (i.e. including trees and blobs), when for reachability the commits are just enough. Introduce BitmapCalculator to get the bitmap of a commit: either because it is precalculated or generating it with a walk only over commits. Change-Id: Ibb6c78affe9eeaf1fa362a06daf4fd2d91c1caea Signed-off-by: Ivan Frade --- .../eclipse/jgit/revwalk/BitmapCalculatorTest.java | 139 +++++++++++++++++++++ .../org/eclipse/jgit/revwalk/BitmapCalculator.java | 93 ++++++++++++++ 2 files changed, 232 insertions(+) create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java new file mode 100644 index 0000000000..3a78e1e623 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java @@ -0,0 +1,139 @@ +package org.eclipse.jgit.revwalk; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import org.eclipse.jgit.internal.storage.file.FileRepository; +import org.eclipse.jgit.internal.storage.file.GC; +import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase; +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.lib.NullProgressMonitor; +import org.eclipse.jgit.lib.ProgressMonitor; +import org.junit.Before; +import org.junit.Test; + +public class BitmapCalculatorTest extends LocalDiskRepositoryTestCase { + TestRepository repo; + + /** {@inheritDoc} */ + @Override + @Before + public void setUp() throws Exception { + super.setUp(); + FileRepository db = createWorkRepository(); + repo = new TestRepository<>(db); + } + + @Test + public void addOnlyCommits() throws Exception { + RevBlob abBlob = repo.blob("a_b_content"); + RevCommit root = repo.commit().add("a/b", abBlob).create(); + repo.update("refs/heads/master", root); + + // GC creates bitmap index with ALL objects + GC gc = new GC(repo.getRepository()); + gc.setAuto(false); + gc.gc(); + + // These objects are not in the bitmap index. + RevBlob acBlob = repo.blob("a_c_content"); + RevCommit head = repo.commit().parent(root).add("a/c", acBlob).create(); + repo.update("refs/heads/master", head); + + BitmapCalculator bitmapWalker = new BitmapCalculator(repo.getRevWalk()); + BitmapBuilder bitmap = bitmapWalker + .getBitmap(head, NullProgressMonitor.INSTANCE); + + assertTrue(bitmap.contains(root.getId())); + assertTrue(bitmap.contains(root.getTree().getId())); + assertTrue(bitmap.contains(abBlob.getId())); + + // BitmapCalculator added only the commit, no other objects. + assertTrue(bitmap.contains(head.getId())); + assertFalse(bitmap.contains(head.getTree().getId())); + assertFalse(bitmap.contains(acBlob.getId())); + } + + @Test + public void walkUntilBitmap() throws Exception { + RevCommit root = repo.commit().create(); + repo.update("refs/heads/master", root); + + // GC creates bitmap index with ALL objects + GC gc = new GC(repo.getRepository()); + gc.setAuto(false); + gc.gc(); + + // These objects are not in the bitmap index. + RevCommit commit1 = repo.commit(root); + RevCommit commit2 = repo.commit(commit1); + repo.update("refs/heads/master", commit2); + + CounterProgressMonitor monitor = new CounterProgressMonitor(); + BitmapCalculator bitmapWalker = new BitmapCalculator(repo.getRevWalk()); + BitmapBuilder bitmap = bitmapWalker.getBitmap(commit2, monitor); + + assertTrue(bitmap.contains(root)); + assertTrue(bitmap.contains(commit1)); + assertTrue(bitmap.contains(commit2)); + assertEquals(2, monitor.getUpdates()); + } + + @Test + public void noNeedToWalk() throws Exception { + RevCommit root = repo.commit().create(); + RevCommit commit1 = repo.commit(root); + RevCommit commit2 = repo.commit(commit1); + repo.update("refs/heads/master", commit2); + + // GC creates bitmap index with ALL objects + GC gc = new GC(repo.getRepository()); + gc.setAuto(false); + gc.gc(); + + CounterProgressMonitor monitor = new CounterProgressMonitor(); + BitmapCalculator bitmapWalker = new BitmapCalculator(repo.getRevWalk()); + BitmapBuilder bitmap = bitmapWalker.getBitmap(commit2, monitor); + + assertTrue(bitmap.contains(root)); + assertTrue(bitmap.contains(commit1)); + assertTrue(bitmap.contains(commit2)); + assertEquals(0, monitor.getUpdates()); + } + + private static class CounterProgressMonitor implements ProgressMonitor { + + private int counter; + + @Override + public void start(int totalTasks) { + // Nothing to do in tests + } + + @Override + public void beginTask(String title, int totalWork) { + // Nothing to to in tests + } + + @Override + public void update(int completed) { + counter += 1; + } + + @Override + public void endTask() { + // Nothing to do in tests + } + + @Override + public boolean isCancelled() { + return false; + } + + int getUpdates() { + return counter; + } + } +} \ No newline at end of file diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java new file mode 100644 index 0000000000..e1d5d4adad --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java @@ -0,0 +1,93 @@ +package org.eclipse.jgit.revwalk; + +import static java.util.Objects.requireNonNull; + +import java.io.IOException; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.internal.revwalk.AddToBitmapFilter; +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.ProgressMonitor; + +/** + * Calculate the bitmap indicating what other commits are reachable from certain + * commit. + *

+ * This bitmap refers only to commits. For a bitmap with ALL objects reachable + * from certain object, see {@code BitmapWalker}. + */ +class BitmapCalculator { + + private final RevWalk walk; + private final BitmapIndex bitmapIndex; + + BitmapCalculator(RevWalk walk) throws IOException { + this.walk = walk; + this.bitmapIndex = requireNonNull( + walk.getObjectReader().getBitmapIndex()); + } + + /** + * Get the reachability bitmap from certain commit to other commits. + *

+ * This will return a precalculated bitmap if available or walk building one + * until finding a precalculated bitmap (and returning the union). + *

+ * Beware that the returned bitmap it is guaranteed to include ONLY the + * commits reachable from the initial commit. It COULD include other objects + * (because precalculated bitmaps have them) but caller shouldn't count on + * that. See {@link BitmapWalker} for a full reachability bitmap. + * + * @param start + * the commit. Use {@code walk.parseCommit(objectId)} to get this + * object from the id. + * @param pm + * progress monitor. Updated by one per commit browsed in the + * graph + * @return the bitmap of reachable commits (and maybe some extra objects) + * for the commit + * @throws MissingObjectException + * the supplied id doesn't exist + * @throws IncorrectObjectTypeException + * the supplied id doens't refer to a commit or a tag + * @throws IOException + */ + BitmapBuilder getBitmap(RevCommit start, ProgressMonitor pm) + throws MissingObjectException, + IncorrectObjectTypeException, IOException { + Bitmap precalculatedBitmap = bitmapIndex.getBitmap(start); + if (precalculatedBitmap != null) { + return asBitmapBuilder(precalculatedBitmap); + } + + walk.reset(); + walk.sort(RevSort.TOPO); + walk.markStart(start); + // Unbounded walk. If the repo has bitmaps, it should bump into one at + // some point. + + BitmapBuilder bitmapResult = bitmapIndex.newBitmapBuilder(); + walk.setRevFilter(new AddToBitmapFilter(bitmapResult)); + while (walk.next() != null) { + // Iterate through all of the commits. The BitmapRevFilter does + // the work. + // + // filter.include returns true for commits that do not have + // a bitmap in bitmapIndex and are not reachable from a + // bitmap in bitmapIndex encountered earlier in the walk. + // Thus the number of commits returned by next() measures how + // much history was traversed without being able to make use + // of bitmaps. + pm.update(1); + } + + return bitmapResult; + } + + private BitmapBuilder asBitmapBuilder(Bitmap bitmap) { + return bitmapIndex.newBitmapBuilder().or(bitmap); + } +} -- cgit v1.2.3 From 601b0ae577014e18929961f03a1940bc192d4ef4 Mon Sep 17 00:00:00 2001 From: Ivan Frade Date: Mon, 22 Apr 2019 15:38:45 -0700 Subject: BitmappedReachabilityChecker: Reachability check using bitmaps The "basic" reachability check walks the graph starting from the tips marking things as "uninteresting". If the target commit is marked as "uninteresting" it was reached; it is reachable from those tips. This requires a lot of walking and can be solved directly with bitmaps. Most of the time the bitmaps are already calculated or a short walk away. This should improve the performance of reachability checks, for example in Gitiles. Change-Id: I83d33271f58d95d2dc9ed151967b3eda513c99f7 Signed-off-by: Ivan Frade --- .../revwalk/BitmappedReachabilityCheckerTest.java | 69 ++++++++++++ .../jgit/revwalk/BitmappedReachabilityChecker.java | 122 +++++++++++++++++++++ 2 files changed, 191 insertions(+) create mode 100644 org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java create mode 100644 org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java 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 new file mode 100644 index 0000000000..5d3adf5eab --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java @@ -0,0 +1,69 @@ +/* + * Copyright (C) 2019, Google LLC + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.eclipse.jgit.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/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java new file mode 100644 index 0000000000..e4d28458a8 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java @@ -0,0 +1,122 @@ +/* + * Copyright (C) 2019, Google LLC + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +package org.eclipse.jgit.revwalk; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Collection; +import java.util.List; +import java.util.Optional; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.lib.NullProgressMonitor; + +/** + * Checks the reachability using bitmaps. + * + * @since 5.5 + */ +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 of the collection + */ + @Override + public Optional areAllReachable(Collection targets, + Collection starters) throws MissingObjectException, + IncorrectObjectTypeException, IOException { + BitmapCalculator calculator = new BitmapCalculator(walk); + + /** + * Iterate over starters bitmaps and remove targets as they become + * reachable. + * + * Building the total starters bitmap has the same cost (iterating over + * all starters adding the bitmaps) and this gives us the chance to + * shorcut the loop. + * + * This is based on the assuption that most of the starters will have + * the reachability bitmap precalculated. If many require a walk, the + * walk.reset() could start to take too much time. + */ + List remainingTargets = new ArrayList<>(targets); + for (RevCommit starter : starters) { + BitmapBuilder starterBitmap = calculator.getBitmap(starter, + NullProgressMonitor.INSTANCE); + remainingTargets.removeIf(starterBitmap::contains); + if (remainingTargets.isEmpty()) { + return Optional.empty(); + } + } + + return Optional.of(remainingTargets.get(0)); + } + +} -- cgit v1.2.3 From 7b96bd812e95d5aa87ea05b30d3e717360bdce20 Mon Sep 17 00:00:00 2001 From: Ivan Frade Date: Wed, 8 May 2019 16:43:04 -0700 Subject: UploadPack: Use reachability checker to validate non-advertised wants In "Reachable commit" request validators, we need to check that a "want" in the request, that hasn't been advertised, is reachable from the refs visible to the user. Current code has intermixed the translation of ObjectIds to RevCommits (and its error handling) with the actual walk, with the delegation to bitmaps in restricted circunstances. Refactor the code to make it "flatter" and more readable. Move ObjectIds to RevCommits translation to its own functions. Use the reachability checker instead of a newly defined walk. Before the non-advertised wants were validated with bitmaps only if any "want" refered to an non-commit. Now they will be validated with bitmaps also if the "wants" refer all to commits. Change-Id: Ib925a48cde89672b07a88bba4e24d0457546baff Signed-off-by: Ivan Frade --- .../src/org/eclipse/jgit/transport/UploadPack.java | 122 +++++++++++++-------- 1 file changed, 78 insertions(+), 44 deletions(-) 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 27090f4383..dff0f9c29a 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java @@ -44,12 +44,11 @@ package org.eclipse.jgit.transport; import static java.util.Collections.unmodifiableMap; -import static org.eclipse.jgit.util.RefMap.toRefMap; import static org.eclipse.jgit.lib.Constants.R_TAGS; import static org.eclipse.jgit.transport.GitProtocolConstants.CAPABILITY_REF_IN_WANT; +import static org.eclipse.jgit.transport.GitProtocolConstants.CAPABILITY_SERVER_OPTION; import static org.eclipse.jgit.transport.GitProtocolConstants.COMMAND_FETCH; import static org.eclipse.jgit.transport.GitProtocolConstants.COMMAND_LS_REFS; -import static org.eclipse.jgit.transport.GitProtocolConstants.CAPABILITY_SERVER_OPTION; import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_AGENT; import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_ALLOW_REACHABLE_SHA1_IN_WANT; import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_ALLOW_TIP_SHA1_IN_WANT; @@ -65,6 +64,7 @@ import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_SHALLOW; import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_SIDE_BAND; import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_SIDE_BAND_64K; import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_THIN_PACK; +import static org.eclipse.jgit.util.RefMap.toRefMap; import java.io.ByteArrayOutputStream; import java.io.EOFException; @@ -80,8 +80,10 @@ import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Objects; +import java.util.Optional; import java.util.Set; import java.util.TreeMap; +import java.util.stream.Collectors; import org.eclipse.jgit.annotations.NonNull; import org.eclipse.jgit.annotations.Nullable; @@ -104,8 +106,11 @@ import org.eclipse.jgit.lib.RefDatabase; import org.eclipse.jgit.lib.Repository; import org.eclipse.jgit.revwalk.AsyncRevObjectQueue; import org.eclipse.jgit.revwalk.BitmapWalker; +import org.eclipse.jgit.revwalk.BitmappedReachabilityChecker; import org.eclipse.jgit.revwalk.DepthWalk; import org.eclipse.jgit.revwalk.ObjectWalk; +import org.eclipse.jgit.revwalk.PedestrianReachabilityChecker; +import org.eclipse.jgit.revwalk.ReachabilityChecker; import org.eclipse.jgit.revwalk.RevCommit; import org.eclipse.jgit.revwalk.RevFlag; import org.eclipse.jgit.revwalk.RevFlagSet; @@ -1867,59 +1872,88 @@ public class UploadPack { private static void checkNotAdvertisedWants(UploadPack up, List notAdvertisedWants, Set reachableFrom) - throws MissingObjectException, IncorrectObjectTypeException, IOException { - // Walk the requested commits back to the provided set of commits. If any - // commit exists, a branch was deleted or rewound and the repository owner - // no longer exports that requested item. If the requested commit is merged - // into an advertised branch it will be marked UNINTERESTING and no commits - // return. + throws IOException { ObjectReader reader = up.getRevWalk().getObjectReader(); try (RevWalk walk = new RevWalk(reader)) { - walk.setRetainBody(false); - AsyncRevObjectQueue q = walk.parseAny(notAdvertisedWants, true); - try { - RevObject obj; - while ((obj = q.next()) != null) { - if (!(obj instanceof RevCommit)) { - // If unadvertized non-commits are requested, use - // bitmaps. If there are no bitmaps, instead of - // incurring the expense of a manual walk, reject - // the request. - BitmapIndex bitmapIndex = reader.getBitmapIndex(); - if (bitmapIndex != null) { - checkNotAdvertisedWantsUsingBitmap( - reader, - bitmapIndex, - notAdvertisedWants, - reachableFrom); - return; - } - throw new WantNotValidException(obj); - } - walk.markStart((RevCommit) obj); + // Missing "wants" throw exception here + List wantsAsObjs = objectIdsToRevObjects(walk, + notAdvertisedWants); + List wantsAsCommits = wantsAsObjs.stream() + .filter(obj -> obj instanceof RevCommit) + .map(obj -> (RevCommit) obj) + .collect(Collectors.toList()); + boolean allWantsAreCommits = wantsAsObjs.size() == wantsAsCommits + .size(); + boolean repoHasBitmaps = reader.getBitmapIndex() != null; + + if (!allWantsAreCommits) { + if (!repoHasBitmaps) { + // If unadvertized non-commits are requested, use + // bitmaps. If there are no bitmaps, instead of + // incurring the expense of a manual walk, reject + // the request. + RevObject nonCommit = wantsAsObjs + .stream() + .filter(obj -> !(obj instanceof RevCommit)) + .limit(1) + .collect(Collectors.toList()).get(0); + throw new WantNotValidException(nonCommit); + } - } catch (MissingObjectException notFound) { - throw new WantNotValidException(notFound.getObjectId(), - notFound); - } finally { - q.release(); + checkNotAdvertisedWantsUsingBitmap(reader, + reader.getBitmapIndex(), notAdvertisedWants, + reachableFrom); + return; } - for (ObjectId id : reachableFrom) { - try { - walk.markUninteresting(walk.parseCommit(id)); - } catch (IncorrectObjectTypeException notCommit) { - continue; - } + + // All wants are commits, we can use ReachabilityChecker + ReachabilityChecker reachabilityChecker = repoHasBitmaps + ? new BitmappedReachabilityChecker(walk) + : new PedestrianReachabilityChecker(true, walk); + + List starters = objectIdsToRevCommits(walk, + reachableFrom); + Optional unreachable = reachabilityChecker + .areAllReachable(wantsAsCommits, starters); + if (unreachable.isPresent()) { + throw new WantNotValidException(unreachable.get()); } - RevCommit bad = walk.next(); - if (bad != null) { - throw new WantNotValidException(bad); + } catch (MissingObjectException notFound) { + throw new WantNotValidException(notFound.getObjectId(), notFound); + } + } + + // Resolve the ObjectIds into RevObjects. Any missing object raises an + // exception + private static List objectIdsToRevObjects(RevWalk walk, + Iterable objectIds) + throws MissingObjectException, IOException { + List result = new ArrayList<>(); + for (ObjectId objectId : objectIds) { + result.add(walk.parseAny(objectId)); + } + return result; + } + + // Get commits from object ids. If the id is not a commit, ignore it. If the + // id doesn't exist, report the missing object in a exception. + private static List objectIdsToRevCommits(RevWalk walk, + Iterable objectIds) + throws MissingObjectException, IOException { + List result = new ArrayList<>(); + for (ObjectId objectId : objectIds) { + try { + result.add(walk.parseCommit(objectId)); + } catch (IncorrectObjectTypeException e) { + continue; } } + return result; } + private void addCommonBase(RevObject o) { if (!o.has(COMMON)) { o.add(COMMON); -- cgit v1.2.3