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.pgm.debug;
45
46 import static java.lang.Integer.valueOf;
47 import static java.lang.Long.valueOf;
48
49 import java.io.File;
50 import java.lang.management.ManagementFactory;
51 import java.lang.management.ThreadMXBean;
52 import java.lang.reflect.Field;
53 import java.util.ArrayList;
54 import java.util.Collections;
55 import java.util.Comparator;
56 import java.util.List;
57
58 import org.eclipse.jgit.diff.DiffAlgorithm;
59 import org.eclipse.jgit.diff.HistogramDiff;
60 import org.eclipse.jgit.diff.MyersDiff;
61 import org.eclipse.jgit.diff.RawText;
62 import org.eclipse.jgit.diff.RawTextComparator;
63 import org.eclipse.jgit.errors.LargeObjectException;
64 import org.eclipse.jgit.lib.AbbreviatedObjectId;
65 import org.eclipse.jgit.lib.Constants;
66 import org.eclipse.jgit.lib.FileMode;
67 import org.eclipse.jgit.lib.MutableObjectId;
68 import org.eclipse.jgit.lib.ObjectId;
69 import org.eclipse.jgit.lib.ObjectReader;
70 import org.eclipse.jgit.lib.Repository;
71 import org.eclipse.jgit.lib.RepositoryBuilder;
72 import org.eclipse.jgit.lib.RepositoryCache;
73 import org.eclipse.jgit.pgm.Command;
74 import org.eclipse.jgit.pgm.TextBuiltin;
75 import org.eclipse.jgit.pgm.internal.CLIText;
76 import org.eclipse.jgit.revwalk.RevCommit;
77 import org.eclipse.jgit.revwalk.RevWalk;
78 import org.eclipse.jgit.treewalk.TreeWalk;
79 import org.eclipse.jgit.treewalk.filter.TreeFilter;
80 import org.eclipse.jgit.util.FS;
81 import org.kohsuke.args4j.Option;
82
83 @Command(usage = "usage_DiffAlgorithms")
84 class DiffAlgorithms extends TextBuiltin {
85
86 final Algorithm myers = new Algorithm() {
87 DiffAlgorithm create() {
88 return MyersDiff.INSTANCE;
89 }
90 };
91
92 final Algorithm histogram = new Algorithm() {
93 DiffAlgorithm create() {
94 HistogramDiff d = new HistogramDiff();
95 d.setFallbackAlgorithm(null);
96 return d;
97 }
98 };
99
100 final Algorithm histogram_myers = new Algorithm() {
101 DiffAlgorithm create() {
102 HistogramDiff d = new HistogramDiff();
103 d.setFallbackAlgorithm(MyersDiff.INSTANCE);
104 return d;
105 }
106 };
107
108
109
110
111
112
113
114 @Option(name = "--algorithm", multiValued = true, metaVar = "NAME", usage = "Enable algorithm(s)")
115 List<String> algorithms = new ArrayList<String>();
116
117 @Option(name = "--text-limit", metaVar = "LIMIT", usage = "Maximum size in KiB to scan per file revision")
118 int textLimit = 15 * 1024;
119
120 @Option(name = "--repository", aliases = { "-r" }, multiValued = true, metaVar = "GIT_DIR", usage = "Repository to scan")
121 List<File> gitDirs = new ArrayList<File>();
122
123 @Option(name = "--count", metaVar = "LIMIT", usage = "Number of file revisions to be compared")
124 int count = 0;
125
126 private final RawTextComparator cmp = RawTextComparator.DEFAULT;
127
128 private ThreadMXBean mxBean;
129
130 @Override
131 protected boolean requiresRepository() {
132 return false;
133 }
134
135 @Override
136 protected void run() throws Exception {
137 mxBean = ManagementFactory.getThreadMXBean();
138 if (!mxBean.isCurrentThreadCpuTimeSupported())
139 throw die("Current thread CPU time not supported on this JRE");
140
141 if (gitDirs.isEmpty()) {
142 RepositoryBuilder rb = new RepositoryBuilder()
143 .setGitDir(new File(gitdir))
144 .readEnvironment()
145 .findGitDir();
146 if (rb.getGitDir() == null)
147 throw die(CLIText.get().cantFindGitDirectory);
148 gitDirs.add(rb.getGitDir());
149 }
150
151 for (File dir : gitDirs) {
152 RepositoryBuilder rb = new RepositoryBuilder();
153 if (RepositoryCache.FileKey.isGitRepository(dir, FS.DETECTED))
154 rb.setGitDir(dir);
155 else
156 rb.findGitDir(dir);
157
158 Repository db = rb.build();
159 try {
160 run(db);
161 } finally {
162 db.close();
163 }
164 }
165 }
166
167 private void run(Repository db) throws Exception {
168 List<Test> all = init();
169
170 long files = 0;
171 int commits = 0;
172 int minN = Integer.MAX_VALUE;
173 int maxN = 0;
174
175 AbbreviatedObjectId startId;
176 try (ObjectReader or = db.newObjectReader()) {
177 final MutableObjectId id = new MutableObjectId();
178 RevWalk rw = new RevWalk(or);
179 TreeWalk tw = new TreeWalk(or);
180 tw.setFilter(TreeFilter.ANY_DIFF);
181 tw.setRecursive(true);
182
183 ObjectId start = db.resolve(Constants.HEAD);
184 startId = or.abbreviate(start);
185 rw.markStart(rw.parseCommit(start));
186 for (;;) {
187 final RevCommit c = rw.next();
188 if (c == null)
189 break;
190 commits++;
191 if (c.getParentCount() != 1)
192 continue;
193
194 RevCommit p = c.getParent(0);
195 rw.parseHeaders(p);
196 tw.reset(p.getTree(), c.getTree());
197 while (tw.next()) {
198 if (!isFile(tw, 0) || !isFile(tw, 1))
199 continue;
200
201 byte[] raw0;
202 try {
203 tw.getObjectId(id, 0);
204 raw0 = or.open(id).getCachedBytes(textLimit * 1024);
205 } catch (LargeObjectException tooBig) {
206 continue;
207 }
208 if (RawText.isBinary(raw0))
209 continue;
210
211 byte[] raw1;
212 try {
213 tw.getObjectId(id, 1);
214 raw1 = or.open(id).getCachedBytes(textLimit * 1024);
215 } catch (LargeObjectException tooBig) {
216 continue;
217 }
218 if (RawText.isBinary(raw1))
219 continue;
220
221 RawText txt0 = new RawText(raw0);
222 RawText txt1 = new RawText(raw1);
223
224 minN = Math.min(minN, txt0.size() + txt1.size());
225 maxN = Math.max(maxN, txt0.size() + txt1.size());
226
227 for (Test test : all)
228 testOne(test, txt0, txt1);
229 files++;
230 }
231 if (count > 0 && files > count)
232 break;
233 }
234 }
235
236 Collections.sort(all, new Comparator<Test>() {
237 public int compare(Test a, Test b) {
238 int cmp = Long.signum(a.runningTimeNanos - b.runningTimeNanos);
239 if (cmp == 0)
240 cmp = a.algorithm.name.compareTo(b.algorithm.name);
241 return cmp;
242 }
243 });
244
245 if (db.getDirectory() != null) {
246 String name = db.getDirectory().getName();
247 File parent = db.getDirectory().getParentFile();
248 if (name.equals(Constants.DOT_GIT) && parent != null)
249 name = parent.getName();
250 outw.println(name + ": start at " + startId.name());
251 }
252
253 outw.format(" %12d files, %8d commits\n", valueOf(files),
254 valueOf(commits));
255 outw.format(" N=%10d min lines, %8d max lines\n", valueOf(minN),
256 valueOf(maxN));
257
258 outw.format("%-25s %12s ( %12s %12s )\n",
259 "Algorithm", "Time(ns)", "Time(ns) on", "Time(ns) on");
260 outw.format("%-25s %12s ( %12s %12s )\n",
261 "", "", "N=" + minN, "N=" + maxN);
262 outw.println("-----------------------------------------------------"
263 + "----------------");
264
265 for (Test test : all) {
266 outw.format("%-25s %12d ( %12d %12d )",
267 test.algorithm.name,
268 valueOf(test.runningTimeNanos),
269 valueOf(test.minN.runningTimeNanos),
270 valueOf(test.maxN.runningTimeNanos));
271 outw.println();
272 }
273 outw.println();
274 outw.flush();
275 }
276
277 private static boolean isFile(TreeWalk tw, int ithTree) {
278 FileMode fm = tw.getFileMode(ithTree);
279 return FileMode.REGULAR_FILE.equals(fm)
280 || FileMode.EXECUTABLE_FILE.equals(fm);
281 }
282
283 private static final int minCPUTimerTicks = 10;
284
285 private void testOne(Test test, RawText a, RawText b) {
286 final DiffAlgorithm da = test.algorithm.create();
287 int cpuTimeChanges = 0;
288 int cnt = 0;
289
290 final long startTime = mxBean.getCurrentThreadCpuTime();
291 long lastTime = startTime;
292 while (cpuTimeChanges < minCPUTimerTicks) {
293 da.diff(cmp, a, b);
294 cnt++;
295
296 long interimTime = mxBean.getCurrentThreadCpuTime();
297 if (interimTime != lastTime) {
298 cpuTimeChanges++;
299 lastTime = interimTime;
300 }
301 }
302 final long stopTime = mxBean.getCurrentThreadCpuTime();
303 final long runTime = (stopTime - startTime) / cnt;
304
305 test.runningTimeNanos += runTime;
306
307 if (test.minN == null || a.size() + b.size() < test.minN.n) {
308 test.minN = new Run();
309 test.minN.n = a.size() + b.size();
310 test.minN.runningTimeNanos = runTime;
311 }
312
313 if (test.maxN == null || a.size() + b.size() > test.maxN.n) {
314 test.maxN = new Run();
315 test.maxN.n = a.size() + b.size();
316 test.maxN.runningTimeNanos = runTime;
317 }
318 }
319
320 private List<Test> init() {
321 List<Test> all = new ArrayList<Test>();
322
323 try {
324 for (Field f : DiffAlgorithms.class.getDeclaredFields()) {
325 if (f.getType() == Algorithm.class) {
326 f.setAccessible(true);
327 Algorithm alg = (Algorithm) f.get(this);
328 alg.name = f.getName();
329 if (included(alg.name, algorithms)) {
330 Test test = new Test();
331 test.algorithm = alg;
332 all.add(test);
333 }
334 }
335 }
336 } catch (IllegalArgumentException e) {
337 throw die("Cannot determine names", e);
338 } catch (IllegalAccessException e) {
339 throw die("Cannot determine names", e);
340 }
341
342 return all;
343 }
344
345 private static boolean included(String name, List<String> want) {
346 if (want.isEmpty())
347 return true;
348 for (String s : want) {
349 if (s.equalsIgnoreCase(name))
350 return true;
351 }
352 return false;
353 }
354
355 private static abstract class Algorithm {
356 String name;
357
358 abstract DiffAlgorithm create();
359 }
360
361 private static class Test {
362 Algorithm algorithm;
363
364 long runningTimeNanos;
365
366 Run minN;
367
368 Run maxN;
369 }
370
371 private static class Run {
372 int n;
373
374 long runningTimeNanos;
375 }
376 }