blob: 02514526d09bba213bf43eb7a02996e9c67c1802 (
plain)
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
/*
* Copyright (C) 2019, Google LLC and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.revwalk;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;
import java.util.stream.Stream;
import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.lib.BitmapIndex;
import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.revwalk.filter.RevFilter;
/**
* Checks the reachability using bitmaps.
*/
class BitmappedReachabilityChecker implements ReachabilityChecker {
private final RevWalk walk;
/**
* @param walk
* walk on the repository to get or create the bitmaps for the
* commits. It must have bitmaps.
* @throws AssertionError
* runtime exception if walk is over a repository without
* bitmaps
* @throws IOException
* if the index or the object reader cannot be opened.
*/
public BitmappedReachabilityChecker(RevWalk walk)
throws IOException {
this.walk = walk;
if (walk.getObjectReader().getBitmapIndex() == null) {
throw new AssertionError(
"Trying to use bitmapped reachability check " //$NON-NLS-1$
+ "on a repository without bitmaps"); //$NON-NLS-1$
}
}
/**
* Check all targets are reachable from the starters.
* <p>
* In this implementation, it is recommended to put the most popular
* starters (e.g. refs/heads tips) at the beginning.
*/
@Override
public Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
Stream<RevCommit> starters) throws MissingObjectException,
IncorrectObjectTypeException, IOException {
List<RevCommit> remainingTargets = new ArrayList<>(targets);
walk.reset();
walk.sort(RevSort.TOPO);
// Filter emits only commits that are unreachable from previously
// visited commits. Internally it keeps a bitmap of everything
// reachable so far, which we use to discard reachable targets.
BitmapIndex repoBitmaps = walk.getObjectReader().getBitmapIndex();
ReachedFilter reachedFilter = new ReachedFilter(repoBitmaps);
walk.setRevFilter(reachedFilter);
Iterator<RevCommit> startersIter = starters.iterator();
while (startersIter.hasNext()) {
walk.markStart(startersIter.next());
while (walk.next() != null) {
remainingTargets.removeIf(reachedFilter::isReachable);
if (remainingTargets.isEmpty()) {
return Optional.empty();
}
}
walk.reset();
}
return Optional.of(remainingTargets.get(0));
}
/**
* This filter emits commits that were not bitmap-reachable from anything
* visited before. Or in other words, commits that add something (themselves
* or their bitmap) to the "reached" bitmap.
*
* Current progress can be queried via {@link #isReachable(RevCommit)}.
*/
private static class ReachedFilter extends RevFilter {
private final BitmapIndex repoBitmaps;
private final BitmapBuilder reached;
/**
* Create a filter that emits only previously unreachable commits.
*
* @param repoBitmaps
* bitmap index of the repo
*/
public ReachedFilter(BitmapIndex repoBitmaps) {
this.repoBitmaps = repoBitmaps;
this.reached = repoBitmaps.newBitmapBuilder();
}
/** {@inheritDoc} */
@Override
public final boolean include(RevWalk walker, RevCommit cmit) {
Bitmap commitBitmap;
if (reached.contains(cmit)) {
// already seen or included
dontFollow(cmit);
return false;
}
if ((commitBitmap = repoBitmaps.getBitmap(cmit)) != null) {
reached.or(commitBitmap);
// Emit the commit because there are new contents in the bitmap
// but don't follow parents (they are already in the bitmap)
dontFollow(cmit);
return true;
}
// No bitmaps, keep going
reached.addObject(cmit, Constants.OBJ_COMMIT);
return true;
}
private static final void dontFollow(RevCommit cmit) {
for (RevCommit p : cmit.getParents()) {
p.add(RevFlag.SEEN);
}
}
/** {@inheritDoc} */
@Override
public final RevFilter clone() {
throw new UnsupportedOperationException();
}
/** {@inheritDoc} */
@Override
public final boolean requiresCommitBody() {
return false;
}
boolean isReachable(RevCommit commit) {
return reached.contains(commit);
}
}
}
|
