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