1 /*
2 * Copyright (C) 2019, Google LLC
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43 package org.eclipse.jgit.revwalk;
44
45 import java.io.IOException;
46 import java.util.ArrayList;
47 import java.util.Collection;
48 import java.util.List;
49 import java.util.Optional;
50
51 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
52 import org.eclipse.jgit.errors.MissingObjectException;
53 import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
54 import org.eclipse.jgit.lib.NullProgressMonitor;
55
56 /**
57 * Checks the reachability using bitmaps.
58 */
59 class BitmappedReachabilityChecker implements ReachabilityChecker {
60
61 private final RevWalk walk;
62
63 /**
64 * @param walk
65 * walk on the repository to get or create the bitmaps for the
66 * commits. It must have bitmaps.
67 * @throws AssertionError
68 * runtime exception if walk is over a repository without
69 * bitmaps
70 * @throws IOException
71 * if the index or the object reader cannot be opened.
72 */
73 public BitmappedReachabilityChecker(RevWalk walk)
74 throws IOException {
75 this.walk = walk;
76 if (walk.getObjectReader().getBitmapIndex() == null) {
77 throw new AssertionError(
78 "Trying to use bitmapped reachability check " //$NON-NLS-1$
79 + "on a repository without bitmaps"); //$NON-NLS-1$
80 }
81 }
82
83 /**
84 * Check all targets are reachable from the starters.
85 * <p>
86 * In this implementation, it is recommended to put the most popular
87 * starters (e.g. refs/heads tips) at the beginning of the collection
88 */
89 @Override
90 public Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
91 Collection<RevCommit> starters) throws MissingObjectException,
92 IncorrectObjectTypeException, IOException {
93 BitmapCalculator calculator = new BitmapCalculator(walk);
94
95 /**
96 * Iterate over starters bitmaps and remove targets as they become
97 * reachable.
98 *
99 * Building the total starters bitmap has the same cost (iterating over
100 * all starters adding the bitmaps) and this gives us the chance to
101 * shorcut the loop.
102 *
103 * This is based on the assuption that most of the starters will have
104 * the reachability bitmap precalculated. If many require a walk, the
105 * walk.reset() could start to take too much time.
106 */
107 List<RevCommit> remainingTargets = new ArrayList<>(targets);
108 for (RevCommit starter : starters) {
109 BitmapBuilder starterBitmap = calculator.getBitmap(starter,
110 NullProgressMonitor.INSTANCE);
111 remainingTargets.removeIf(starterBitmap::contains);
112 if (remainingTargets.isEmpty()) {
113 return Optional.empty();
114 }
115 }
116
117 return Optional.of(remainingTargets.get(0));
118 }
119
120 }