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