1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 package org.eclipse.jgit.internal.storage.pack;
45
46 import static org.eclipse.jgit.internal.storage.file.PackBitmapIndex.FLAG_REUSE;
47
48 import java.io.IOException;
49 import java.util.ArrayList;
50 import java.util.Collection;
51 import java.util.Collections;
52 import java.util.Comparator;
53 import java.util.HashSet;
54 import java.util.Iterator;
55 import java.util.List;
56 import java.util.Set;
57
58 import com.googlecode.javaewah.EWAHCompressedBitmap;
59
60 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
61 import org.eclipse.jgit.errors.MissingObjectException;
62 import org.eclipse.jgit.internal.JGitText;
63 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl;
64 import org.eclipse.jgit.internal.storage.file.PackBitmapIndex;
65 import org.eclipse.jgit.internal.storage.file.PackBitmapIndexBuilder;
66 import org.eclipse.jgit.internal.storage.file.PackBitmapIndexRemapper;
67 import org.eclipse.jgit.lib.AnyObjectId;
68 import org.eclipse.jgit.lib.Constants;
69 import org.eclipse.jgit.lib.ObjectId;
70 import org.eclipse.jgit.lib.ObjectReader;
71 import org.eclipse.jgit.lib.ProgressMonitor;
72 import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
73 import org.eclipse.jgit.revwalk.ObjectWalk;
74 import org.eclipse.jgit.revwalk.RevCommit;
75 import org.eclipse.jgit.revwalk.RevObject;
76 import org.eclipse.jgit.revwalk.RevWalk;
77 import org.eclipse.jgit.util.BlockList;
78
79
80 class PackWriterBitmapPreparer {
81
82 private static final Comparator<BitmapBuilder> BUILDER_BY_CARDINALITY_DSC =
83 new Comparator<BitmapBuilder>() {
84 public int compare(BitmapBuilder a, BitmapBuilder b) {
85 return Integer.signum(b.cardinality() - a.cardinality());
86 }
87 };
88
89 private final ObjectReader reader;
90 private final ProgressMonitor pm;
91 private final Set<? extends ObjectId> want;
92 private final PackBitmapIndexBuilder writeBitmaps;
93 private final BitmapIndexImpl commitBitmapIndex;
94 private final PackBitmapIndexRemapper bitmapRemapper;
95 private final BitmapIndexImpl bitmapIndex;
96 private final int minCommits = 100;
97 private final int maxCommits = 5000;
98
99 PackWriterBitmapPreparer(ObjectReader reader,
100 PackBitmapIndexBuilder writeBitmaps, ProgressMonitor pm,
101 Set<? extends ObjectId> want) throws IOException {
102 this.reader = reader;
103 this.writeBitmaps = writeBitmaps;
104 this.pm = pm;
105 this.want = want;
106 this.commitBitmapIndex = new BitmapIndexImpl(writeBitmaps);
107 this.bitmapRemapper = PackBitmapIndexRemapper.newPackBitmapIndex(
108 reader.getBitmapIndex(), writeBitmaps);
109 this.bitmapIndex = new BitmapIndexImpl(bitmapRemapper);
110 }
111
112 Collection<BitmapCommit> doCommitSelection(int expectedNumCommits)
113 throws MissingObjectException, IncorrectObjectTypeException,
114 IOException {
115 pm.beginTask(JGitText.get().selectingCommits, ProgressMonitor.UNKNOWN);
116 RevWalk rw = new RevWalk(reader);
117 rw.setRetainBody(false);
118 WalkResult result = findPaths(rw, expectedNumCommits);
119 pm.endTask();
120
121 int totCommits = result.commitsByOldest.length - result.commitStartPos;
122 BlockList<BitmapCommit> selections = new BlockList<BitmapCommit>(
123 totCommits / minCommits + 1);
124 for (BitmapCommit reuse : result.reuse)
125 selections.add(reuse);
126
127 if (totCommits == 0) {
128 for (AnyObjectId id : result.peeledWant)
129 selections.add(new BitmapCommit(id, false, 0));
130 return selections;
131 }
132
133 pm.beginTask(JGitText.get().selectingCommits, totCommits);
134
135 for (BitmapBuilder bitmapableCommits : result.paths) {
136 int cardinality = bitmapableCommits.cardinality();
137
138 List<List<BitmapCommit>> running = new ArrayList<
139 List<BitmapCommit>>();
140
141
142
143 int index = -1;
144 int nextIn = nextSelectionDistance(0, cardinality);
145 int nextFlg = nextIn == maxCommits ? PackBitmapIndex.FLAG_REUSE : 0;
146 boolean mustPick = nextIn == 0;
147 for (RevCommit c : result) {
148 if (!bitmapableCommits.contains(c))
149 continue;
150
151 index++;
152 nextIn--;
153 pm.update(1);
154
155
156 if (result.peeledWant.remove(c)) {
157 if (nextIn > 0)
158 nextFlg = 0;
159 } else if (!mustPick && ((nextIn > 0)
160 || (c.getParentCount() <= 1 && nextIn > -minCommits))) {
161 continue;
162 }
163
164 int flags = nextFlg;
165 nextIn = nextSelectionDistance(index, cardinality);
166 nextFlg = nextIn == maxCommits ? PackBitmapIndex.FLAG_REUSE : 0;
167 mustPick = nextIn == 0;
168
169 BitmapBuilder fullBitmap = commitBitmapIndex.newBitmapBuilder();
170 rw.reset();
171 rw.markStart(c);
172 for (AnyObjectId objectId : result.reuse)
173 rw.markUninteresting(rw.parseCommit(objectId));
174 rw.setRevFilter(
175 PackWriterBitmapWalker.newRevFilter(null, fullBitmap));
176
177 while (rw.next() != null) {
178
179 }
180
181 List<List<BitmapCommit>> matches = new ArrayList<
182 List<BitmapCommit>>();
183 for (List<BitmapCommit> list : running) {
184 BitmapCommit last = list.get(list.size() - 1);
185 if (fullBitmap.contains(last))
186 matches.add(list);
187 }
188
189 List<BitmapCommit> match;
190 if (matches.isEmpty()) {
191 match = new ArrayList<BitmapCommit>();
192 running.add(match);
193 } else {
194 match = matches.get(0);
195
196 for (List<BitmapCommit> list : matches) {
197 if (list.size() > match.size())
198 match = list;
199 }
200 }
201 match.add(new BitmapCommit(c, !match.isEmpty(), flags));
202 writeBitmaps.addBitmap(c, fullBitmap, 0);
203 }
204
205 for (List<BitmapCommit> list : running)
206 selections.addAll(list);
207 }
208 writeBitmaps.clearBitmaps();
209
210
211 for (AnyObjectId remainingWant : result.peeledWant)
212 selections.add(new BitmapCommit(remainingWant, false, 0));
213
214 pm.endTask();
215 return selections;
216 }
217
218 private WalkResult findPaths(RevWalk rw, int expectedNumCommits)
219 throws MissingObjectException, IOException {
220 BitmapBuilder reuseBitmap = commitBitmapIndex.newBitmapBuilder();
221 List<BitmapCommit> reuse = new ArrayList<BitmapCommit>();
222 for (PackBitmapIndexRemapper.Entry entry : bitmapRemapper) {
223 if ((entry.getFlags() & FLAG_REUSE) != FLAG_REUSE)
224 continue;
225
226 RevObject ro = rw.peel(rw.parseAny(entry));
227 if (ro instanceof RevCommit) {
228 RevCommit rc = (RevCommit) ro;
229 reuse.add(new BitmapCommit(rc, false, entry.getFlags()));
230 rw.markUninteresting(rc);
231
232 EWAHCompressedBitmap bitmap = bitmapRemapper.ofObjectType(
233 bitmapRemapper.getBitmap(rc), Constants.OBJ_COMMIT);
234 writeBitmaps.addBitmap(rc, bitmap, 0);
235 reuseBitmap.add(rc, Constants.OBJ_COMMIT);
236 }
237 }
238 writeBitmaps.clearBitmaps();
239
240
241
242 List<BitmapBuilder> paths = new ArrayList<BitmapBuilder>(want.size());
243 Set<RevCommit> peeledWant = new HashSet<RevCommit>(want.size());
244 for (AnyObjectId objectId : want) {
245 RevObject ro = rw.peel(rw.parseAny(objectId));
246 if (ro instanceof RevCommit && !reuseBitmap.contains(ro)) {
247 RevCommit rc = (RevCommit) ro;
248 peeledWant.add(rc);
249 rw.markStart(rc);
250
251 BitmapBuilder bitmap = commitBitmapIndex.newBitmapBuilder();
252 bitmap.or(reuseBitmap);
253 bitmap.add(rc, Constants.OBJ_COMMIT);
254 paths.add(bitmap);
255 }
256 }
257
258
259
260 RevCommit[] commits = new RevCommit[expectedNumCommits];
261 int pos = commits.length;
262 RevCommit rc;
263 while ((rc = rw.next()) != null) {
264 commits[--pos] = rc;
265 for (BitmapBuilder path : paths) {
266 if (path.contains(rc)) {
267 for (RevCommit c : rc.getParents())
268 path.add(c, Constants.OBJ_COMMIT);
269 }
270 }
271
272 pm.update(1);
273 }
274
275
276 if (!reuse.isEmpty())
277 for (BitmapBuilder bitmap : paths)
278 bitmap.andNot(reuseBitmap);
279
280
281 List<BitmapBuilder> distinctPaths = new ArrayList<BitmapBuilder>(paths.size());
282 while (!paths.isEmpty()) {
283 Collections.sort(paths, BUILDER_BY_CARDINALITY_DSC);
284 BitmapBuilder largest = paths.remove(0);
285 distinctPaths.add(largest);
286
287
288
289 for (int i = paths.size() - 1; i >= 0; i--)
290 paths.get(i).andNot(largest);
291 }
292
293 return new WalkResult(peeledWant, commits, pos, distinctPaths, reuse);
294 }
295
296 private int nextSelectionDistance(int idx, int cardinality) {
297 if (idx > cardinality)
298 throw new IllegalArgumentException();
299 int idxFromStart = cardinality - idx;
300 int mustRegionEnd = 100;
301 if (idxFromStart <= mustRegionEnd)
302 return 0;
303
304
305 int minRegionEnd = 20000;
306 if (idxFromStart <= minRegionEnd)
307 return Math.min(idxFromStart - mustRegionEnd, minCommits);
308
309
310 int next = Math.min(idxFromStart - minRegionEnd, maxCommits);
311 return Math.max(next, minCommits);
312 }
313
314 PackWriterBitmapWalker newBitmapWalker() {
315 return new PackWriterBitmapWalker(
316 new ObjectWalk(reader), bitmapIndex, null);
317 }
318
319 static final class BitmapCommit extends ObjectId {
320 private final boolean reuseWalker;
321 private final int flags;
322
323 private BitmapCommit(
324 AnyObjectId objectId, boolean reuseWalker, int flags) {
325 super(objectId);
326 this.reuseWalker = reuseWalker;
327 this.flags = flags;
328 }
329
330 boolean isReuseWalker() {
331 return reuseWalker;
332 }
333
334 int getFlags() {
335 return flags;
336 }
337 }
338
339 private static final class WalkResult implements Iterable<RevCommit> {
340 private final Set<? extends ObjectId> peeledWant;
341 private final RevCommit[] commitsByOldest;
342 private final int commitStartPos;
343 private final List<BitmapBuilder> paths;
344 private final Iterable<BitmapCommit> reuse;
345
346 private WalkResult(Set<? extends ObjectId> peeledWant,
347 RevCommit[] commitsByOldest, int commitStartPos,
348 List<BitmapBuilder> paths, Iterable<BitmapCommit> reuse) {
349 this.peeledWant = peeledWant;
350 this.commitsByOldest = commitsByOldest;
351 this.commitStartPos = commitStartPos;
352 this.paths = paths;
353 this.reuse = reuse;
354 }
355
356 public Iterator<RevCommit> iterator() {
357 return new Iterator<RevCommit>() {
358 int pos = commitStartPos;
359
360 public boolean hasNext() {
361 return pos < commitsByOldest.length;
362 }
363
364 public RevCommit next() {
365 return commitsByOldest[pos++];
366 }
367
368 public void remove() {
369 throw new UnsupportedOperationException();
370 }
371 };
372 }
373 }
374 }