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 import static org.eclipse.jgit.revwalk.RevFlag.SEEN;
48
49 import java.io.IOException;
50 import java.util.ArrayList;
51 import java.util.Collection;
52 import java.util.Collections;
53 import java.util.Comparator;
54 import java.util.HashSet;
55 import java.util.Iterator;
56 import java.util.List;
57 import java.util.Set;
58
59 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
60 import org.eclipse.jgit.errors.MissingObjectException;
61 import org.eclipse.jgit.internal.JGitText;
62 import org.eclipse.jgit.internal.revwalk.AddUnseenToBitmapFilter;
63 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl;
64 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl.CompressedBitmap;
65 import org.eclipse.jgit.internal.storage.file.PackBitmapIndex;
66 import org.eclipse.jgit.internal.storage.file.PackBitmapIndexBuilder;
67 import org.eclipse.jgit.internal.storage.file.PackBitmapIndexRemapper;
68 import org.eclipse.jgit.lib.AnyObjectId;
69 import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
70 import org.eclipse.jgit.lib.Constants;
71 import org.eclipse.jgit.lib.ObjectId;
72 import org.eclipse.jgit.lib.ObjectReader;
73 import org.eclipse.jgit.lib.ProgressMonitor;
74 import org.eclipse.jgit.revwalk.BitmapWalker;
75 import org.eclipse.jgit.revwalk.ObjectWalk;
76 import org.eclipse.jgit.revwalk.RevCommit;
77 import org.eclipse.jgit.revwalk.RevObject;
78 import org.eclipse.jgit.revwalk.RevWalk;
79 import org.eclipse.jgit.revwalk.filter.RevFilter;
80 import org.eclipse.jgit.storage.pack.PackConfig;
81 import org.eclipse.jgit.util.BlockList;
82 import org.eclipse.jgit.util.SystemReader;
83
84 import com.googlecode.javaewah.EWAHCompressedBitmap;
85
86
87
88
89
90 class PackWriterBitmapPreparer {
91
92 private static final int DAY_IN_SECONDS = 24 * 60 * 60;
93
94 private static final Comparator<RevCommit> ORDER_BY_REVERSE_TIMESTAMP = (
95 RevCommit a, RevCommit b) -> Integer
96 .signum(b.getCommitTime() - a.getCommitTime());
97
98 private final ObjectReader reader;
99 private final ProgressMonitor pm;
100 private final Set<? extends ObjectId> want;
101 private final PackBitmapIndexBuilder writeBitmaps;
102 private final BitmapIndexImpl commitBitmapIndex;
103 private final PackBitmapIndexRemapper bitmapRemapper;
104 private final BitmapIndexImpl bitmapIndex;
105
106 private final int contiguousCommitCount;
107 private final int recentCommitCount;
108 private final int recentCommitSpan;
109 private final int distantCommitSpan;
110 private final int excessiveBranchCount;
111 private final long inactiveBranchTimestamp;
112
113 PackWriterBitmapPreparer(ObjectReader reader,
114 PackBitmapIndexBuilder writeBitmaps, ProgressMonitor pm,
115 Set<? extends ObjectId> want, PackConfig config)
116 throws IOException {
117 this.reader = reader;
118 this.writeBitmaps = writeBitmaps;
119 this.pm = pm;
120 this.want = want;
121 this.commitBitmapIndex = new BitmapIndexImpl(writeBitmaps);
122 this.bitmapRemapper = PackBitmapIndexRemapper.newPackBitmapIndex(
123 reader.getBitmapIndex(), writeBitmaps);
124 this.bitmapIndex = new BitmapIndexImpl(bitmapRemapper);
125 this.contiguousCommitCount = config.getBitmapContiguousCommitCount();
126 this.recentCommitCount = config.getBitmapRecentCommitCount();
127 this.recentCommitSpan = config.getBitmapRecentCommitSpan();
128 this.distantCommitSpan = config.getBitmapDistantCommitSpan();
129 this.excessiveBranchCount = config.getBitmapExcessiveBranchCount();
130 long now = SystemReader.getInstance().getCurrentTime();
131 long ageInSeconds = config.getBitmapInactiveBranchAgeInDays()
132 * DAY_IN_SECONDS;
133 this.inactiveBranchTimestamp = (now / 1000) - ageInSeconds;
134 }
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151 Collection<BitmapCommit> selectCommits(int expectedCommitCount,
152 Set<? extends ObjectId> excludeFromBitmapSelection)
153 throws IncorrectObjectTypeException, IOException,
154 MissingObjectException {
155
156
157
158
159
160
161
162
163 try (RevWalkvwalk/RevWalk.html#RevWalk">RevWalk rw = new RevWalk(reader);
164 RevWalk rw2 = new RevWalk(reader)) {
165 pm.beginTask(JGitText.get().selectingCommits,
166 ProgressMonitor.UNKNOWN);
167 rw.setRetainBody(false);
168 CommitSelectionHelper selectionHelper = captureOldAndNewCommits(rw,
169 expectedCommitCount, excludeFromBitmapSelection);
170 pm.endTask();
171
172
173
174
175 int newCommits = selectionHelper.getCommitCount();
176 BlockList<BitmapCommit> selections = new BlockList<>(
177 selectionHelper.reusedCommits.size()
178 + newCommits / recentCommitSpan + 1);
179 for (BitmapCommit reuse : selectionHelper.reusedCommits) {
180 selections.add(reuse);
181 }
182
183 if (newCommits == 0) {
184 for (AnyObjectId id : selectionHelper.newWants) {
185 selections.add(new BitmapCommit(id, false, 0));
186 }
187 return selections;
188 }
189
190 pm.beginTask(JGitText.get().selectingCommits, newCommits);
191 int totalWants = want.size();
192 BitmapBuilder seen = commitBitmapIndex.newBitmapBuilder();
193 seen.or(selectionHelper.reusedCommitsBitmap);
194 rw2.setRetainBody(false);
195 rw2.setRevFilter(new NotInBitmapFilter(seen));
196
197
198
199
200
201 for (RevCommit rc : selectionHelper.newWantsByNewest) {
202 BitmapBuilder tipBitmap = commitBitmapIndex.newBitmapBuilder();
203 rw2.markStart((RevCommit) rw2.peel(rw2.parseAny(rc)));
204 RevCommit rc2;
205 while ((rc2 = rw2.next()) != null) {
206 tipBitmap.addObject(rc2, Constants.OBJ_COMMIT);
207 }
208 int cardinality = tipBitmap.cardinality();
209 seen.or(tipBitmap);
210
211
212
213
214
215
216
217 List<List<BitmapCommit>> chains = new ArrayList<>();
218
219
220
221
222
223 boolean isActiveBranch = true;
224 if (totalWants > excessiveBranchCount && !isRecentCommit(rc)) {
225 isActiveBranch = false;
226 }
227
228
229
230
231 int index = -1;
232 int nextIn = nextSpan(cardinality);
233 int nextFlg = nextIn == distantCommitSpan
234 ? PackBitmapIndex.FLAG_REUSE
235 : 0;
236
237
238
239 for (RevCommit c : selectionHelper) {
240
241
242 int distanceFromTip = cardinality - index - 1;
243 if (distanceFromTip == 0) {
244 break;
245 }
246
247
248 if (!tipBitmap.contains(c)) {
249 continue;
250 }
251
252 index++;
253 nextIn--;
254 pm.update(1);
255
256
257 if (selectionHelper.newWants.remove(c)) {
258 if (nextIn > 0) {
259 nextFlg = 0;
260 }
261 } else {
262 boolean stillInSpan = nextIn >= 0;
263 boolean isMergeCommit = c.getParentCount() > 1;
264
265
266
267
268 boolean mustPick = (nextIn <= -recentCommitSpan)
269 || (isActiveBranch
270 && (distanceFromTip <= contiguousCommitCount))
271 || (distanceFromTip == 1);
272 if (!mustPick && (stillInSpan || !isMergeCommit)) {
273 continue;
274 }
275 }
276
277
278
279 int flags = nextFlg;
280 nextIn = nextSpan(distanceFromTip);
281 nextFlg = nextIn == distantCommitSpan
282 ? PackBitmapIndex.FLAG_REUSE
283 : 0;
284
285
286 BitmapBuilder bitmap = commitBitmapIndex.newBitmapBuilder();
287 rw.reset();
288 rw.markStart(c);
289 rw.setRevFilter(new AddUnseenToBitmapFilter(
290 selectionHelper.reusedCommitsBitmap, bitmap));
291 while (rw.next() != null) {
292
293 }
294
295
296
297
298 List<BitmapCommit> longestAncestorChain = null;
299 for (List<BitmapCommit> chain : chains) {
300 BitmapCommit mostRecentCommit = chain
301 .get(chain.size() - 1);
302 if (bitmap.contains(mostRecentCommit)) {
303 if (longestAncestorChain == null
304 || longestAncestorChain.size() < chain
305 .size()) {
306 longestAncestorChain = chain;
307 }
308 }
309 }
310
311 if (longestAncestorChain == null) {
312 longestAncestorChain = new ArrayList<>();
313 chains.add(longestAncestorChain);
314 }
315 longestAncestorChain.add(new BitmapCommit(c,
316 !longestAncestorChain.isEmpty(), flags));
317 writeBitmaps.addBitmap(c, bitmap, 0);
318 }
319
320 for (List<BitmapCommit> chain : chains) {
321 selections.addAll(chain);
322 }
323 }
324 writeBitmaps.clearBitmaps();
325
326
327 for (AnyObjectId remainingWant : selectionHelper.newWants) {
328 selections.add(new BitmapCommit(remainingWant, false, 0));
329 }
330
331 pm.endTask();
332 return selections;
333 }
334 }
335
336 private boolean isRecentCommit(RevCommit revCommit) {
337 return revCommit.getCommitTime() > inactiveBranchTimestamp;
338 }
339
340
341
342
343
344
345
346
347
348
349
350 private static class NotInBitmapFilter extends RevFilter {
351 private final BitmapBuilder bitmap;
352
353 NotInBitmapFilter(BitmapBuilder bitmap) {
354 this.bitmap = bitmap;
355 }
356
357 @Override
358 public final boolean include(RevWalk rw, RevCommit c) {
359 if (!bitmap.contains(c)) {
360 return true;
361 }
362 for (RevCommit p : c.getParents()) {
363 p.add(SEEN);
364 }
365 return false;
366 }
367
368 @Override
369 public final NotInBitmapFilter clone() {
370 throw new UnsupportedOperationException();
371 }
372
373 @Override
374 public final boolean requiresCommitBody() {
375 return false;
376 }
377 }
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400 private CommitSelectionHelper captureOldAndNewCommits(RevWalk rw,
401 int expectedCommitCount,
402 Set<? extends ObjectId> excludeFromBitmapSelection)
403 throws IncorrectObjectTypeException, IOException,
404 MissingObjectException {
405
406 BitmapBuilder reuse = commitBitmapIndex.newBitmapBuilder();
407 List<BitmapCommit> reuseCommits = new ArrayList<>();
408 for (PackBitmapIndexRemapper.Entry entry : bitmapRemapper) {
409
410 if ((entry.getFlags() & FLAG_REUSE) != FLAG_REUSE) {
411 continue;
412 }
413 RevObject ro = rw.peel(rw.parseAny(entry));
414 if (!(ro instanceof RevCommit)) {
415 continue;
416 }
417
418 RevCommit rc = (RevCommit) ro;
419 reuseCommits.add(new BitmapCommit(rc, false, entry.getFlags()));
420 if (!reuse.contains(rc)) {
421 EWAHCompressedBitmap bitmap = bitmapRemapper.ofObjectType(
422 bitmapRemapper.getBitmap(rc), Constants.OBJ_COMMIT);
423 reuse.or(new CompressedBitmap(bitmap, commitBitmapIndex));
424 }
425 }
426
427
428
429 List<RevCommit> newWantsByNewest = new ArrayList<>(want.size());
430 Set<RevCommit> newWants = new HashSet<>(want.size());
431 for (AnyObjectId objectId : want) {
432 RevObject ro = rw.peel(rw.parseAny(objectId));
433 if (!(ro instanceof RevCommit) || reuse.contains(ro)
434 || excludeFromBitmapSelection.contains(ro)) {
435 continue;
436 }
437
438 RevCommit rc = (RevCommit) ro;
439 rw.markStart(rc);
440 newWants.add(rc);
441 newWantsByNewest.add(rc);
442 }
443
444
445
446 rw.setRevFilter(new NotInBitmapFilter(reuse));
447 RevCommit[] commits = new RevCommit[expectedCommitCount];
448 int pos = commits.length;
449 RevCommit rc;
450 while ((rc = rw.next()) != null && pos > 0) {
451 commits[--pos] = rc;
452 pm.update(1);
453 }
454
455
456 Collections.sort(newWantsByNewest, ORDER_BY_REVERSE_TIMESTAMP);
457 return new CommitSelectionHelper(newWants, commits, pos,
458 newWantsByNewest, reuse, reuseCommits);
459 }
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483 int nextSpan(int distanceFromTip) {
484 if (distanceFromTip < 0) {
485 throw new IllegalArgumentException();
486 }
487
488
489 if (distanceFromTip <= recentCommitCount) {
490 return recentCommitSpan;
491 }
492
493 int next = Math.min(distanceFromTip - recentCommitCount,
494 distantCommitSpan);
495 return Math.max(next, recentCommitSpan);
496 }
497
498 BitmapWalker newBitmapWalker() {
499 return new BitmapWalker(
500 new ObjectWalk(reader), bitmapIndex, null);
501 }
502
503
504
505
506 static final class BitmapCommit extends ObjectId {
507 private final boolean reuseWalker;
508 private final int flags;
509
510 BitmapCommit(AnyObjectId objectId, boolean reuseWalker, int flags) {
511 super(objectId);
512 this.reuseWalker = reuseWalker;
513 this.flags = flags;
514 }
515
516 boolean isReuseWalker() {
517 return reuseWalker;
518 }
519
520 int getFlags() {
521 return flags;
522 }
523 }
524
525
526
527
528
529
530
531
532
533
534
535 private static final class CommitSelectionHelper implements Iterable<RevCommit> {
536 final Set<? extends ObjectId> newWants;
537
538 final List<RevCommit> newWantsByNewest;
539 final BitmapBuilder reusedCommitsBitmap;
540
541 final List<BitmapCommit> reusedCommits;
542
543 final RevCommit[] newCommitsByOldest;
544
545 final int newCommitStartPos;
546
547 CommitSelectionHelper(Set<? extends ObjectId> newWants,
548 RevCommit[] commitsByOldest, int commitStartPos,
549 List<RevCommit> newWantsByNewest,
550 BitmapBuilder reusedCommitsBitmap,
551 List<BitmapCommit> reuse) {
552 this.newWants = newWants;
553 this.newCommitsByOldest = commitsByOldest;
554 this.newCommitStartPos = commitStartPos;
555 this.newWantsByNewest = newWantsByNewest;
556 this.reusedCommitsBitmap = reusedCommitsBitmap;
557 this.reusedCommits = reuse;
558 }
559
560 @Override
561 public Iterator<RevCommit> iterator() {
562
563
564 return new Iterator<RevCommit>() {
565 int pos = newCommitStartPos;
566
567 @Override
568 public boolean hasNext() {
569 return pos < newCommitsByOldest.length;
570 }
571
572 @Override
573 public RevCommit next() {
574 return newCommitsByOldest[pos++];
575 }
576
577 @Override
578 public void remove() {
579 throw new UnsupportedOperationException();
580 }
581 };
582 }
583
584 int getCommitCount() {
585 return newCommitsByOldest.length - newCommitStartPos;
586 }
587 }
588 }