Merge branch 'jc/blame' (early part)
[git/git.git] / builtin-rev-list.c
CommitLineData
64745109 1#include "cache.h"
e091eb93 2#include "refs.h"
36f8d174 3#include "tag.h"
64745109 4#include "commit.h"
9de48752
LT
5#include "tree.h"
6#include "blob.h"
1b0c7174 7#include "tree-walk.h"
c4e05b1a 8#include "diff.h"
ae563542 9#include "revision.h"
c64ed70d 10#include "list-objects.h"
5fb61b8d 11#include "builtin.h"
ae563542 12
1b65a5aa 13/* bits #0-15 in revision.h */
64745109 14
1b65a5aa 15#define COUNTED (1u<<16)
8906300f 16
a6f68d47 17static const char rev_list_usage[] =
69e0c256
JH
18"git-rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
19" limiting output:\n"
20" --max-count=nr\n"
21" --max-age=epoch\n"
22" --min-age=epoch\n"
23" --sparse\n"
24" --no-merges\n"
93b74bca 25" --remove-empty\n"
69e0c256 26" --all\n"
42cabc34 27" --stdin\n"
69e0c256 28" ordering output:\n"
69e0c256 29" --topo-order\n"
4c8725f1 30" --date-order\n"
69e0c256
JH
31" formatting output:\n"
32" --parents\n"
c6496575 33" --objects | --objects-edge\n"
69e0c256
JH
34" --unpacked\n"
35" --header | --pretty\n"
9da5c2f0 36" --abbrev=nr | --no-abbrev\n"
5c51c985 37" --abbrev-commit\n"
b24bace5 38" --left-right\n"
69e0c256 39" special purpose:\n"
457f08a0
JH
40" --bisect\n"
41" --bisect-vars"
69e0c256 42;
a6f68d47 43
5fb61b8d 44static struct rev_info revs;
ae563542 45
96f1e58f
DR
46static int bisect_list;
47static int show_timestamp;
48static int hdr_termination;
91539833 49static const char *header_prefix;
e646de0d 50
81f2bb1f
LT
51static void show_commit(struct commit *commit)
52{
dc68c4ff
JH
53 if (show_timestamp)
54 printf("%lu ", commit->date);
91539833
LT
55 if (header_prefix)
56 fputs(header_prefix, stdout);
384e99a4
JH
57 if (commit->object.flags & BOUNDARY)
58 putchar('-');
74bd9029 59 else if (revs.left_right) {
577ed5c2
JH
60 if (commit->object.flags & SYMMETRIC_LEFT)
61 putchar('<');
62 else
63 putchar('>');
64 }
7594c4b2
JH
65 if (revs.abbrev_commit && revs.abbrev)
66 fputs(find_unique_abbrev(commit->object.sha1, revs.abbrev),
67 stdout);
5c51c985
JH
68 else
69 fputs(sha1_to_hex(commit->object.sha1), stdout);
7b0c9966 70 if (revs.parents) {
81f2bb1f
LT
71 struct commit_list *parents = commit->parents;
72 while (parents) {
88494423 73 struct object *o = &(parents->item->object);
81f2bb1f 74 parents = parents->next;
88494423
JH
75 if (o->flags & TMP_MARK)
76 continue;
77 printf(" %s", sha1_to_hex(o->sha1));
78 o->flags |= TMP_MARK;
81f2bb1f 79 }
88494423
JH
80 /* TMP_MARK is a general purpose flag that can
81 * be used locally, but the user should clean
82 * things up after it is done with them.
83 */
84 for (parents = commit->parents;
85 parents;
86 parents = parents->next)
87 parents->item->object.flags &= ~TMP_MARK;
81f2bb1f 88 }
7594c4b2 89 if (revs.commit_format == CMIT_FMT_ONELINE)
d87449c5
JH
90 putchar(' ');
91 else
92 putchar('\n');
93
7594c4b2 94 if (revs.verbose_header) {
000182ea 95 static char pretty_header[16384];
7594c4b2
JH
96 pretty_print_commit(revs.commit_format, commit, ~0,
97 pretty_header, sizeof(pretty_header),
a7b02ccf 98 revs.abbrev, NULL, NULL, revs.date_mode);
000182ea 99 printf("%s%c", pretty_header, hdr_termination);
7620d39f
LT
100 }
101 fflush(stdout);
cb115748
LT
102 if (commit->parents) {
103 free_commit_list(commit->parents);
104 commit->parents = NULL;
105 }
4cac42b1
JH
106 free(commit->buffer);
107 commit->buffer = NULL;
a3437b8c
JS
108}
109
c64ed70d 110static void show_object(struct object_array_entry *p)
9de48752 111{
c64ed70d
JH
112 /* An object with name "foo\n0000000..." can be used to
113 * confuse downstream git-pack-objects very badly.
114 */
115 const char *ep = strchr(p->name, '\n');
b9849a1a
JH
116
117 if (p->item->type == OBJ_BLOB && !has_sha1_file(p->item->sha1))
118 die("missing blob object '%s'", sha1_to_hex(p->item->sha1));
119
c64ed70d
JH
120 if (ep) {
121 printf("%s %.*s\n", sha1_to_hex(p->item->sha1),
122 (int) (ep - p->name),
123 p->name);
9de48752 124 }
c64ed70d
JH
125 else
126 printf("%s %s\n", sha1_to_hex(p->item->sha1), p->name);
9de48752
LT
127}
128
8d1d8f83
JH
129static void show_edge(struct commit *commit)
130{
131 printf("-%s\n", sha1_to_hex(commit->object.sha1));
132}
133
8b3a1e05
LT
134/*
135 * This is a truly stupid algorithm, but it's only
136 * used for bisection, and we just don't care enough.
137 *
138 * We care just barely enough to avoid recursing for
139 * non-merge entries.
140 */
141static int count_distance(struct commit_list *entry)
142{
143 int nr = 0;
144
145 while (entry) {
146 struct commit *commit = entry->item;
147 struct commit_list *p;
148
149 if (commit->object.flags & (UNINTERESTING | COUNTED))
150 break;
8efdc326 151 if (!revs.prune_fn || (commit->object.flags & TREECHANGE))
b3cfd939 152 nr++;
8b3a1e05
LT
153 commit->object.flags |= COUNTED;
154 p = commit->parents;
155 entry = p;
156 if (p) {
157 p = p->next;
158 while (p) {
159 nr += count_distance(p);
160 p = p->next;
161 }
162 }
163 }
b3cfd939 164
8b3a1e05
LT
165 return nr;
166}
167
3d958064 168static void clear_distance(struct commit_list *list)
8b3a1e05
LT
169{
170 while (list) {
171 struct commit *commit = list->item;
172 commit->object.flags &= ~COUNTED;
173 list = list->next;
174 }
175}
176
1daa09d9 177#define DEBUG_BISECT 0
1c4fea3a
JH
178
179static inline int weight(struct commit_list *elem)
180{
181 return *((int*)(elem->item->util));
182}
183
184static inline void weight_set(struct commit_list *elem, int weight)
185{
186 *((int*)(elem->item->util)) = weight;
187}
188
1daa09d9 189static int count_interesting_parents(struct commit *commit)
1c4fea3a 190{
1daa09d9
JH
191 struct commit_list *p;
192 int count;
193
194 for (count = 0, p = commit->parents; p; p = p->next) {
195 if (p->item->object.flags & UNINTERESTING)
196 continue;
197 count++;
1c4fea3a 198 }
1daa09d9 199 return count;
1c4fea3a
JH
200}
201
2a464690
JH
202static inline int halfway(struct commit_list *p, int distance, int nr)
203{
204 /*
205 * Don't short-cut something we are not going to return!
206 */
207 if (revs.prune_fn && !(p->item->object.flags & TREECHANGE))
208 return 0;
1daa09d9
JH
209 if (DEBUG_BISECT)
210 return 0;
2a464690
JH
211 /*
212 * 2 and 3 are halfway of 5.
213 * 3 is halfway of 6 but 2 and 4 are not.
214 */
215 distance *= 2;
216 switch (distance - nr) {
217 case -1: case 0: case 1:
218 return 1;
219 default:
220 return 0;
221 }
222}
223
1daa09d9
JH
224#if !DEBUG_BISECT
225#define show_list(a,b,c,d) do { ; } while (0)
226#else
227static void show_list(const char *debug, int counted, int nr,
228 struct commit_list *list)
1c4fea3a 229{
1daa09d9
JH
230 struct commit_list *p;
231
232 fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
233
234 for (p = list; p; p = p->next) {
235 struct commit_list *pp;
236 struct commit *commit = p->item;
237 unsigned flags = commit->object.flags;
238 enum object_type type;
239 unsigned long size;
240 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
241 char *ep, *sp;
242
243 fprintf(stderr, "%c%c%c ",
244 (flags & TREECHANGE) ? 'T' : ' ',
245 (flags & UNINTERESTING) ? 'U' : ' ',
246 (flags & COUNTED) ? 'C' : ' ');
247 if (commit->util)
248 fprintf(stderr, "%3d", weight(p));
249 else
250 fprintf(stderr, "---");
251 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
252 for (pp = commit->parents; pp; pp = pp->next)
253 fprintf(stderr, " %.*s", 8,
254 sha1_to_hex(pp->item->object.sha1));
255
256 sp = strstr(buf, "\n\n");
257 if (sp) {
258 sp += 2;
259 for (ep = sp; *ep && *ep != '\n'; ep++)
260 ;
261 fprintf(stderr, " %.*s", (int)(ep - sp), sp);
262 }
263 fprintf(stderr, "\n");
264 }
265}
266#endif /* DEBUG_BISECT */
267
268/*
269 * zero or positive weight is the number of interesting commits it can
270 * reach, including itself. Especially, weight = 0 means it does not
271 * reach any tree-changing commits (e.g. just above uninteresting one
272 * but traversal is with pathspec).
273 *
274 * weight = -1 means it has one parent and its distance is yet to
275 * be computed.
276 *
277 * weight = -2 means it has more than one parent and its distance is
278 * unknown. After running count_distance() first, they will get zero
279 * or positive distance.
280 */
281
282static struct commit_list *find_bisection(struct commit_list *list,
283 int *reaches, int *all)
284{
285 int n, nr, on_list, counted, distance;
286 struct commit_list *p, *best, *next, *last;
1c4fea3a
JH
287 int *weights;
288
1daa09d9
JH
289 show_list("bisection 2 entry", 0, 0, list);
290
291 /*
292 * Count the number of total and tree-changing items on the
293 * list, while reversing the list.
294 */
295 for (nr = on_list = 0, last = NULL, p = list;
296 p;
297 p = next) {
298 unsigned flags = p->item->object.flags;
299
300 next = p->next;
301 if (flags & UNINTERESTING)
302 continue;
303 p->next = last;
304 last = p;
305 if (!revs.prune_fn || (flags & TREECHANGE))
1c4fea3a 306 nr++;
1daa09d9 307 on_list++;
1c4fea3a 308 }
1daa09d9
JH
309 list = last;
310 show_list("bisection 2 sorted", 0, nr, list);
311
1c4fea3a 312 *all = nr;
1daa09d9 313 weights = xcalloc(on_list, sizeof(int*));
1c4fea3a
JH
314 counted = 0;
315
316 for (n = 0, p = list; p; p = p->next) {
1daa09d9
JH
317 struct commit *commit = p->item;
318 unsigned flags = commit->object.flags;
319
320 p->item->util = &weights[n++];
321 switch (count_interesting_parents(commit)) {
322 case 0:
323 if (!revs.prune_fn || (flags & TREECHANGE)) {
1c4fea3a
JH
324 weight_set(p, 1);
325 counted++;
1daa09d9
JH
326 show_list("bisection 2 count one",
327 counted, nr, list);
1c4fea3a 328 }
1daa09d9
JH
329 /*
330 * otherwise, it is known not to reach any
331 * tree-changing commit and gets weight 0.
332 */
333 break;
334 case 1:
335 weight_set(p, -1);
336 break;
337 default:
338 weight_set(p, -2);
339 break;
1c4fea3a
JH
340 }
341 }
342
1daa09d9
JH
343 show_list("bisection 2 initialize", counted, nr, list);
344
1c4fea3a
JH
345 /*
346 * If you have only one parent in the resulting set
347 * then you can reach one commit more than that parent
348 * can reach. So we do not have to run the expensive
349 * count_distance() for single strand of pearls.
350 *
351 * However, if you have more than one parents, you cannot
352 * just add their distance and one for yourself, since
353 * they usually reach the same ancestor and you would
354 * end up counting them twice that way.
355 *
356 * So we will first count distance of merges the usual
357 * way, and then fill the blanks using cheaper algorithm.
358 */
359 for (p = list; p; p = p->next) {
1daa09d9 360 if (p->item->object.flags & UNINTERESTING)
1c4fea3a
JH
361 continue;
362 n = weight(p);
1daa09d9 363 if (n != -2)
1c4fea3a
JH
364 continue;
365 distance = count_distance(p);
1daa09d9 366 clear_distance(list);
1c4fea3a
JH
367 weight_set(p, distance);
368
369 /* Does it happen to be at exactly half-way? */
2a464690 370 if (halfway(p, distance, nr)) {
1c4fea3a 371 p->next = NULL;
2a464690 372 *reaches = distance;
1c4fea3a
JH
373 free(weights);
374 return p;
375 }
376 counted++;
377 }
378
1daa09d9
JH
379 show_list("bisection 2 count_distance", counted, nr, list);
380
1c4fea3a
JH
381 while (counted < nr) {
382 for (p = list; p; p = p->next) {
383 struct commit_list *q;
1daa09d9 384 unsigned flags = p->item->object.flags;
1c4fea3a 385
1daa09d9 386 if (0 <= weight(p))
1c4fea3a 387 continue;
1daa09d9
JH
388 for (q = p->item->parents; q; q = q->next) {
389 if (q->item->object.flags & UNINTERESTING)
390 continue;
391 if (0 <= weight(q))
1c4fea3a 392 break;
1daa09d9 393 }
1c4fea3a
JH
394 if (!q)
395 continue;
1daa09d9
JH
396
397 /*
398 * weight for p is unknown but q is known.
399 * add one for p itself if p is to be counted,
400 * otherwise inherit it from q directly.
401 */
402 if (!revs.prune_fn || (flags & TREECHANGE)) {
403 weight_set(p, weight(q)+1);
404 counted++;
405 show_list("bisection 2 count one",
406 counted, nr, list);
407 }
408 else
409 weight_set(p, weight(q));
1c4fea3a
JH
410
411 /* Does it happen to be at exactly half-way? */
2a464690
JH
412 distance = weight(p);
413 if (halfway(p, distance, nr)) {
1c4fea3a 414 p->next = NULL;
2a464690 415 *reaches = distance;
1c4fea3a
JH
416 free(weights);
417 return p;
418 }
419 }
420 }
421
1daa09d9
JH
422 show_list("bisection 2 counted all", counted, nr, list);
423
1c4fea3a 424 /* Then find the best one */
1daa09d9 425 counted = -1;
1c4fea3a
JH
426 best = list;
427 for (p = list; p; p = p->next) {
1daa09d9
JH
428 unsigned flags = p->item->object.flags;
429
430 if (revs.prune_fn && !(flags & TREECHANGE))
1c4fea3a
JH
431 continue;
432 distance = weight(p);
433 if (nr - distance < distance)
434 distance = nr - distance;
435 if (distance > counted) {
436 best = p;
437 counted = distance;
438 *reaches = weight(p);
439 }
440 }
441 if (best)
442 best->next = NULL;
443 free(weights);
444 return best;
445}
446
42cabc34
JH
447static void read_revisions_from_stdin(struct rev_info *revs)
448{
449 char line[1000];
450
451 while (fgets(line, sizeof(line), stdin) != NULL) {
452 int len = strlen(line);
453 if (line[len - 1] == '\n')
454 line[--len] = 0;
455 if (!len)
456 break;
457 if (line[0] == '-')
458 die("options not supported in --stdin mode");
459 if (handle_revision_arg(line, revs, 0, 1))
460 die("bad revision '%s'", line);
461 }
462}
463
a633fca0 464int cmd_rev_list(int argc, const char **argv, const char *prefix)
64745109 465{
ae563542 466 struct commit_list *list;
d9a83684 467 int i;
42cabc34 468 int read_from_stdin = 0;
457f08a0 469 int bisect_show_vars = 0;
64745109 470
256c3fe6 471 git_config(git_default_config);
a633fca0 472 init_revisions(&revs, prefix);
7594c4b2
JH
473 revs.abbrev = 0;
474 revs.commit_format = CMIT_FMT_UNSPECIFIED;
a4a88b2b 475 argc = setup_revisions(argc, argv, &revs, NULL);
ae563542 476
fcfda02b 477 for (i = 1 ; i < argc; i++) {
cf484544 478 const char *arg = argv[i];
fcfda02b 479
a6f68d47 480 if (!strcmp(arg, "--header")) {
7594c4b2 481 revs.verbose_header = 1;
9d97aa64
LT
482 continue;
483 }
dc68c4ff
JH
484 if (!strcmp(arg, "--timestamp")) {
485 show_timestamp = 1;
486 continue;
487 }
8b3a1e05
LT
488 if (!strcmp(arg, "--bisect")) {
489 bisect_list = 1;
490 continue;
491 }
457f08a0
JH
492 if (!strcmp(arg, "--bisect-vars")) {
493 bisect_list = 1;
494 bisect_show_vars = 1;
495 continue;
496 }
42cabc34
JH
497 if (!strcmp(arg, "--stdin")) {
498 if (read_from_stdin++)
499 die("--stdin given twice?");
500 read_revisions_from_stdin(&revs);
501 continue;
502 }
ae563542 503 usage(rev_list_usage);
a6f68d47 504
fcfda02b 505 }
7594c4b2
JH
506 if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
507 /* The command line has a --pretty */
508 hdr_termination = '\n';
509 if (revs.commit_format == CMIT_FMT_ONELINE)
91539833 510 header_prefix = "";
7594c4b2 511 else
91539833 512 header_prefix = "commit ";
7594c4b2 513 }
db89665f
JH
514 else if (revs.verbose_header)
515 /* Only --header was specified */
516 revs.commit_format = CMIT_FMT_RAW;
fcfda02b 517
ae563542 518 list = revs.commits;
ae563542 519
8c1f0b44
JH
520 if ((!list &&
521 (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
1f1e895f 522 !revs.pending.nr)) ||
8c1f0b44 523 revs.diff)
7b34c2fa
LT
524 usage(rev_list_usage);
525
2d10c555 526 save_commit_buffer = revs.verbose_header || revs.grep_filter;
9181ca2c 527 track_object_refs = 0;
4e1dc640
JH
528 if (bisect_list)
529 revs.limited = 1;
9181ca2c 530
a4a88b2b
LT
531 prepare_revision_walk(&revs);
532 if (revs.tree_objects)
8d1d8f83 533 mark_edges_uninteresting(revs.commits, &revs, show_edge);
a4a88b2b 534
457f08a0
JH
535 if (bisect_list) {
536 int reaches = reaches, all = all;
537
1daa09d9 538 revs.commits = find_bisection(revs.commits, &reaches, &all);
457f08a0
JH
539 if (bisect_show_vars) {
540 int cnt;
541 if (!revs.commits)
542 return 1;
543 /*
544 * revs.commits can reach "reaches" commits among
545 * "all" commits. If it is good, then there are
546 * (all-reaches) commits left to be bisected.
547 * On the other hand, if it is bad, then the set
548 * to bisect is "reaches".
549 * A bisect set of size N has (N-1) commits further
550 * to test, as we already know one bad one.
551 */
552 cnt = all-reaches;
553 if (cnt < reaches)
554 cnt = reaches;
555 printf("bisect_rev=%s\n"
556 "bisect_nr=%d\n"
557 "bisect_good=%d\n"
558 "bisect_bad=%d\n"
559 "bisect_all=%d\n",
560 sha1_to_hex(revs.commits->item->object.sha1),
561 cnt - 1,
562 all - reaches - 1,
563 reaches - 1,
564 all);
565 return 0;
566 }
567 }
7b34c2fa 568
c64ed70d 569 traverse_commit_list(&revs, show_commit, show_object);
8906300f 570
64745109
LT
571 return 0;
572}