1
2
3
4
5
6
7
8
9
10 package org.eclipse.jgit.internal.revwalk;
11
12 import java.io.IOException;
13 import java.util.ArrayList;
14 import java.util.Collection;
15 import java.util.Iterator;
16 import java.util.List;
17 import java.util.Optional;
18 import java.util.stream.Stream;
19
20 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
21 import org.eclipse.jgit.errors.MissingObjectException;
22 import org.eclipse.jgit.lib.BitmapIndex;
23 import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
24 import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
25 import org.eclipse.jgit.lib.Constants;
26 import org.eclipse.jgit.revwalk.ReachabilityChecker;
27 import org.eclipse.jgit.revwalk.RevCommit;
28 import org.eclipse.jgit.revwalk.RevFlag;
29 import org.eclipse.jgit.revwalk.RevSort;
30 import org.eclipse.jgit.revwalk.RevWalk;
31 import org.eclipse.jgit.revwalk.filter.RevFilter;
32
33
34
35
36 public class BitmappedReachabilityChecker implements ReachabilityChecker {
37
38 private final RevWalk walk;
39
40
41
42
43
44
45
46
47
48
49
50 public BitmappedReachabilityChecker(RevWalk walk)
51 throws IOException {
52 this.walk = walk;
53 if (walk.getObjectReader().getBitmapIndex() == null) {
54 throw new AssertionError(
55 "Trying to use bitmapped reachability check "
56 + "on a repository without bitmaps");
57 }
58 }
59
60
61
62
63
64
65
66 @Override
67 public Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
68 Stream<RevCommit> starters) throws MissingObjectException,
69 IncorrectObjectTypeException, IOException {
70
71 List<RevCommit> remainingTargets = new ArrayList<>(targets);
72
73 walk.reset();
74 walk.sort(RevSort.TOPO);
75
76
77
78
79 BitmapIndex repoBitmaps = walk.getObjectReader().getBitmapIndex();
80 ReachedFilter reachedFilter = new ReachedFilter(repoBitmaps);
81 walk.setRevFilter(reachedFilter);
82
83 Iterator<RevCommit> startersIter = starters.iterator();
84 while (startersIter.hasNext()) {
85 walk.markStart(startersIter.next());
86 while (walk.next() != null) {
87 remainingTargets.removeIf(reachedFilter::isReachable);
88
89 if (remainingTargets.isEmpty()) {
90 return Optional.empty();
91 }
92 }
93 walk.reset();
94 }
95
96 return Optional.of(remainingTargets.get(0));
97 }
98
99
100
101
102
103
104
105
106 private static class ReachedFilter extends RevFilter {
107
108 private final BitmapIndex repoBitmaps;
109 private final BitmapBuilder reached;
110
111
112
113
114
115
116
117 public ReachedFilter(BitmapIndex repoBitmaps) {
118 this.repoBitmaps = repoBitmaps;
119 this.reached = repoBitmaps.newBitmapBuilder();
120 }
121
122
123 @Override
124 public final boolean include(RevWalk walker, RevCommit cmit) {
125 Bitmap commitBitmap;
126
127 if (reached.contains(cmit)) {
128
129 dontFollow(cmit);
130 return false;
131 }
132
133 if ((commitBitmap = repoBitmaps.getBitmap(cmit)) != null) {
134 reached.or(commitBitmap);
135
136
137 dontFollow(cmit);
138 return true;
139 }
140
141
142 reached.addObject(cmit, Constants.OBJ_COMMIT);
143 return true;
144 }
145
146 private static final void dontFollow(RevCommit cmit) {
147 for (RevCommit p : cmit.getParents()) {
148 p.add(RevFlag.SEEN);
149 }
150 }
151
152
153 @Override
154 public final RevFilter clone() {
155 throw new UnsupportedOperationException();
156 }
157
158
159 @Override
160 public final boolean requiresCommitBody() {
161 return false;
162 }
163
164 boolean isReachable(RevCommit commit) {
165 return reached.contains(commit);
166 }
167 }
168 }