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