10 #include "list-objects.h"
15 /* bits #0-15 in revision.h */
17 #define COUNTED (1u<<16)
19 static const char rev_list_usage
[] =
20 "git rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
38 " formatting output:\n"
41 " --objects | --objects-edge\n"
43 " --header | --pretty\n"
44 " --abbrev=nr | --no-abbrev\n"
53 static struct rev_info revs
;
55 static int bisect_list
;
56 static int show_timestamp
;
57 static int hdr_termination
;
58 static const char *header_prefix
;
60 static void finish_commit(struct commit
*commit
);
61 static void show_commit(struct commit
*commit
)
63 graph_show_commit(revs
.graph
);
66 printf("%lu ", commit
->date
);
68 fputs(header_prefix
, stdout
);
71 if (commit
->object
.flags
& BOUNDARY
)
73 else if (commit
->object
.flags
& UNINTERESTING
)
75 else if (revs
.left_right
) {
76 if (commit
->object
.flags
& SYMMETRIC_LEFT
)
82 if (revs
.abbrev_commit
&& revs
.abbrev
)
83 fputs(find_unique_abbrev(commit
->object
.sha1
, revs
.abbrev
),
86 fputs(sha1_to_hex(commit
->object
.sha1
), stdout
);
87 if (revs
.print_parents
) {
88 struct commit_list
*parents
= commit
->parents
;
90 printf(" %s", sha1_to_hex(parents
->item
->object
.sha1
));
91 parents
= parents
->next
;
94 if (revs
.children
.name
) {
95 struct commit_list
*children
;
97 children
= lookup_decoration(&revs
.children
, &commit
->object
);
99 printf(" %s", sha1_to_hex(children
->item
->object
.sha1
));
100 children
= children
->next
;
103 show_decorations(commit
);
104 if (revs
.commit_format
== CMIT_FMT_ONELINE
)
109 if (revs
.verbose_header
&& commit
->buffer
) {
110 struct strbuf buf
= STRBUF_INIT
;
111 pretty_print_commit(revs
.commit_format
, commit
,
112 &buf
, revs
.abbrev
, NULL
, NULL
,
116 if (revs
.commit_format
!= CMIT_FMT_ONELINE
)
117 graph_show_oneline(revs
.graph
);
119 graph_show_commit_msg(revs
.graph
, &buf
);
122 * Add a newline after the commit message.
124 * Usually, this newline produces a blank
125 * padding line between entries, in which case
126 * we need to add graph padding on this line.
128 * However, the commit message may not end in a
129 * newline. In this case the newline simply
130 * ends the last line of the commit message,
131 * and we don't need any graph output. (This
132 * always happens with CMIT_FMT_ONELINE, and it
133 * happens with CMIT_FMT_USERFORMAT when the
134 * format doesn't explicitly end in a newline.)
136 if (buf
.len
&& buf
.buf
[buf
.len
- 1] == '\n')
137 graph_show_padding(revs
.graph
);
141 * If the message buffer is empty, just show
142 * the rest of the graph output for this
145 if (graph_show_remainder(revs
.graph
))
150 printf("%s%c", buf
.buf
, hdr_termination
);
152 strbuf_release(&buf
);
154 if (graph_show_remainder(revs
.graph
))
157 maybe_flush_or_die(stdout
, "stdout");
158 finish_commit(commit
);
161 static void finish_commit(struct commit
*commit
)
163 if (commit
->parents
) {
164 free_commit_list(commit
->parents
);
165 commit
->parents
= NULL
;
167 free(commit
->buffer
);
168 commit
->buffer
= NULL
;
171 static void finish_object(struct object_array_entry
*p
)
173 if (p
->item
->type
== OBJ_BLOB
&& !has_sha1_file(p
->item
->sha1
))
174 die("missing blob object '%s'", sha1_to_hex(p
->item
->sha1
));
177 static void show_object(struct object_array_entry
*p
)
179 /* An object with name "foo\n0000000..." can be used to
180 * confuse downstream "git pack-objects" very badly.
182 const char *ep
= strchr(p
->name
, '\n');
186 printf("%s %.*s\n", sha1_to_hex(p
->item
->sha1
),
187 (int) (ep
- p
->name
),
191 printf("%s %s\n", sha1_to_hex(p
->item
->sha1
), p
->name
);
194 static void show_edge(struct commit
*commit
)
196 printf("-%s\n", sha1_to_hex(commit
->object
.sha1
));
200 * This is a truly stupid algorithm, but it's only
201 * used for bisection, and we just don't care enough.
203 * We care just barely enough to avoid recursing for
206 static int count_distance(struct commit_list
*entry
)
211 struct commit
*commit
= entry
->item
;
212 struct commit_list
*p
;
214 if (commit
->object
.flags
& (UNINTERESTING
| COUNTED
))
216 if (!(commit
->object
.flags
& TREESAME
))
218 commit
->object
.flags
|= COUNTED
;
224 nr
+= count_distance(p
);
233 static void clear_distance(struct commit_list
*list
)
236 struct commit
*commit
= list
->item
;
237 commit
->object
.flags
&= ~COUNTED
;
242 #define DEBUG_BISECT 0
244 static inline int weight(struct commit_list
*elem
)
246 return *((int*)(elem
->item
->util
));
249 static inline void weight_set(struct commit_list
*elem
, int weight
)
251 *((int*)(elem
->item
->util
)) = weight
;
254 static int count_interesting_parents(struct commit
*commit
)
256 struct commit_list
*p
;
259 for (count
= 0, p
= commit
->parents
; p
; p
= p
->next
) {
260 if (p
->item
->object
.flags
& UNINTERESTING
)
267 static inline int halfway(struct commit_list
*p
, int nr
)
270 * Don't short-cut something we are not going to return!
272 if (p
->item
->object
.flags
& TREESAME
)
277 * 2 and 3 are halfway of 5.
278 * 3 is halfway of 6 but 2 and 4 are not.
280 switch (2 * weight(p
) - nr
) {
281 case -1: case 0: case 1:
289 #define show_list(a,b,c,d) do { ; } while (0)
291 static void show_list(const char *debug
, int counted
, int nr
,
292 struct commit_list
*list
)
294 struct commit_list
*p
;
296 fprintf(stderr
, "%s (%d/%d)\n", debug
, counted
, nr
);
298 for (p
= list
; p
; p
= p
->next
) {
299 struct commit_list
*pp
;
300 struct commit
*commit
= p
->item
;
301 unsigned flags
= commit
->object
.flags
;
302 enum object_type type
;
304 char *buf
= read_sha1_file(commit
->object
.sha1
, &type
, &size
);
307 fprintf(stderr
, "%c%c%c ",
308 (flags
& TREESAME
) ? ' ' : 'T',
309 (flags
& UNINTERESTING
) ? 'U' : ' ',
310 (flags
& COUNTED
) ? 'C' : ' ');
312 fprintf(stderr
, "%3d", weight(p
));
314 fprintf(stderr
, "---");
315 fprintf(stderr
, " %.*s", 8, sha1_to_hex(commit
->object
.sha1
));
316 for (pp
= commit
->parents
; pp
; pp
= pp
->next
)
317 fprintf(stderr
, " %.*s", 8,
318 sha1_to_hex(pp
->item
->object
.sha1
));
320 sp
= strstr(buf
, "\n\n");
323 for (ep
= sp
; *ep
&& *ep
!= '\n'; ep
++)
325 fprintf(stderr
, " %.*s", (int)(ep
- sp
), sp
);
327 fprintf(stderr
, "\n");
330 #endif /* DEBUG_BISECT */
332 static struct commit_list
*best_bisection(struct commit_list
*list
, int nr
)
334 struct commit_list
*p
, *best
;
335 int best_distance
= -1;
338 for (p
= list
; p
; p
= p
->next
) {
340 unsigned flags
= p
->item
->object
.flags
;
342 if (flags
& TREESAME
)
344 distance
= weight(p
);
345 if (nr
- distance
< distance
)
346 distance
= nr
- distance
;
347 if (distance
> best_distance
) {
349 best_distance
= distance
;
357 struct commit
*commit
;
361 static int compare_commit_dist(const void *a_
, const void *b_
)
363 struct commit_dist
*a
, *b
;
365 a
= (struct commit_dist
*)a_
;
366 b
= (struct commit_dist
*)b_
;
367 if (a
->distance
!= b
->distance
)
368 return b
->distance
- a
->distance
; /* desc sort */
369 return hashcmp(a
->commit
->object
.sha1
, b
->commit
->object
.sha1
);
372 static struct commit_list
*best_bisection_sorted(struct commit_list
*list
, int nr
)
374 struct commit_list
*p
;
375 struct commit_dist
*array
= xcalloc(nr
, sizeof(*array
));
378 for (p
= list
, cnt
= 0; p
; p
= p
->next
) {
380 unsigned flags
= p
->item
->object
.flags
;
382 if (flags
& TREESAME
)
384 distance
= weight(p
);
385 if (nr
- distance
< distance
)
386 distance
= nr
- distance
;
387 array
[cnt
].commit
= p
->item
;
388 array
[cnt
].distance
= distance
;
391 qsort(array
, cnt
, sizeof(*array
), compare_commit_dist
);
392 for (p
= list
, i
= 0; i
< cnt
; i
++) {
393 struct name_decoration
*r
= xmalloc(sizeof(*r
) + 100);
394 struct object
*obj
= &(array
[i
].commit
->object
);
396 sprintf(r
->name
, "dist=%d", array
[i
].distance
);
397 r
->next
= add_decoration(&name_decoration
, obj
, r
);
398 p
->item
= array
[i
].commit
;
408 * zero or positive weight is the number of interesting commits it can
409 * reach, including itself. Especially, weight = 0 means it does not
410 * reach any tree-changing commits (e.g. just above uninteresting one
411 * but traversal is with pathspec).
413 * weight = -1 means it has one parent and its distance is yet to
416 * weight = -2 means it has more than one parent and its distance is
417 * unknown. After running count_distance() first, they will get zero
418 * or positive distance.
420 static struct commit_list
*do_find_bisection(struct commit_list
*list
,
421 int nr
, int *weights
,
425 struct commit_list
*p
;
429 for (n
= 0, p
= list
; p
; p
= p
->next
) {
430 struct commit
*commit
= p
->item
;
431 unsigned flags
= commit
->object
.flags
;
433 p
->item
->util
= &weights
[n
++];
434 switch (count_interesting_parents(commit
)) {
436 if (!(flags
& TREESAME
)) {
439 show_list("bisection 2 count one",
443 * otherwise, it is known not to reach any
444 * tree-changing commit and gets weight 0.
456 show_list("bisection 2 initialize", counted
, nr
, list
);
459 * If you have only one parent in the resulting set
460 * then you can reach one commit more than that parent
461 * can reach. So we do not have to run the expensive
462 * count_distance() for single strand of pearls.
464 * However, if you have more than one parents, you cannot
465 * just add their distance and one for yourself, since
466 * they usually reach the same ancestor and you would
467 * end up counting them twice that way.
469 * So we will first count distance of merges the usual
470 * way, and then fill the blanks using cheaper algorithm.
472 for (p
= list
; p
; p
= p
->next
) {
473 if (p
->item
->object
.flags
& UNINTERESTING
)
477 weight_set(p
, count_distance(p
));
478 clear_distance(list
);
480 /* Does it happen to be at exactly half-way? */
481 if (!find_all
&& halfway(p
, nr
))
486 show_list("bisection 2 count_distance", counted
, nr
, list
);
488 while (counted
< nr
) {
489 for (p
= list
; p
; p
= p
->next
) {
490 struct commit_list
*q
;
491 unsigned flags
= p
->item
->object
.flags
;
495 for (q
= p
->item
->parents
; q
; q
= q
->next
) {
496 if (q
->item
->object
.flags
& UNINTERESTING
)
505 * weight for p is unknown but q is known.
506 * add one for p itself if p is to be counted,
507 * otherwise inherit it from q directly.
509 if (!(flags
& TREESAME
)) {
510 weight_set(p
, weight(q
)+1);
512 show_list("bisection 2 count one",
516 weight_set(p
, weight(q
));
518 /* Does it happen to be at exactly half-way? */
519 if (!find_all
&& halfway(p
, nr
))
524 show_list("bisection 2 counted all", counted
, nr
, list
);
527 return best_bisection(list
, nr
);
529 return best_bisection_sorted(list
, nr
);
532 static struct commit_list
*find_bisection(struct commit_list
*list
,
533 int *reaches
, int *all
,
537 struct commit_list
*p
, *best
, *next
, *last
;
540 show_list("bisection 2 entry", 0, 0, list
);
543 * Count the number of total and tree-changing items on the
544 * list, while reversing the list.
546 for (nr
= on_list
= 0, last
= NULL
, p
= list
;
549 unsigned flags
= p
->item
->object
.flags
;
552 if (flags
& UNINTERESTING
)
556 if (!(flags
& TREESAME
))
561 show_list("bisection 2 sorted", 0, nr
, list
);
564 weights
= xcalloc(on_list
, sizeof(*weights
));
566 /* Do the real work of finding bisection commit. */
567 best
= do_find_bisection(list
, nr
, weights
, find_all
);
571 *reaches
= weight(best
);
577 int cmd_rev_list(int argc
, const char **argv
, const char *prefix
)
579 struct commit_list
*list
;
581 int read_from_stdin
= 0;
582 int bisect_show_vars
= 0;
583 int bisect_find_all
= 0;
586 git_config(git_default_config
, NULL
);
587 init_revisions(&revs
, prefix
);
589 revs
.commit_format
= CMIT_FMT_UNSPECIFIED
;
590 argc
= setup_revisions(argc
, argv
, &revs
, NULL
);
592 quiet
= DIFF_OPT_TST(&revs
.diffopt
, QUIET
);
593 for (i
= 1 ; i
< argc
; i
++) {
594 const char *arg
= argv
[i
];
596 if (!strcmp(arg
, "--header")) {
597 revs
.verbose_header
= 1;
600 if (!strcmp(arg
, "--timestamp")) {
604 if (!strcmp(arg
, "--bisect")) {
608 if (!strcmp(arg
, "--bisect-all")) {
613 if (!strcmp(arg
, "--bisect-vars")) {
615 bisect_show_vars
= 1;
618 if (!strcmp(arg
, "--stdin")) {
619 if (read_from_stdin
++)
620 die("--stdin given twice?");
621 read_revisions_from_stdin(&revs
);
624 usage(rev_list_usage
);
627 if (revs
.commit_format
!= CMIT_FMT_UNSPECIFIED
) {
628 /* The command line has a --pretty */
629 hdr_termination
= '\n';
630 if (revs
.commit_format
== CMIT_FMT_ONELINE
)
633 header_prefix
= "commit ";
635 else if (revs
.verbose_header
)
636 /* Only --header was specified */
637 revs
.commit_format
= CMIT_FMT_RAW
;
642 (!(revs
.tag_objects
||revs
.tree_objects
||revs
.blob_objects
) &&
643 !revs
.pending
.nr
)) ||
645 usage(rev_list_usage
);
647 save_commit_buffer
= revs
.verbose_header
||
648 revs
.grep_filter
.pattern_list
;
652 if (prepare_revision_walk(&revs
))
653 die("revision walk setup failed");
654 if (revs
.tree_objects
)
655 mark_edges_uninteresting(revs
.commits
, &revs
, show_edge
);
658 int reaches
= reaches
, all
= all
;
660 revs
.commits
= find_bisection(revs
.commits
, &reaches
, &all
,
662 if (bisect_show_vars
) {
668 * revs.commits can reach "reaches" commits among
669 * "all" commits. If it is good, then there are
670 * (all-reaches) commits left to be bisected.
671 * On the other hand, if it is bad, then the set
672 * to bisect is "reaches".
673 * A bisect set of size N has (N-1) commits further
674 * to test, as we already know one bad one.
679 strcpy(hex
, sha1_to_hex(revs
.commits
->item
->object
.sha1
));
681 if (bisect_find_all
) {
682 traverse_commit_list(&revs
, show_commit
, show_object
);
686 printf("bisect_rev=%s\n"
700 traverse_commit_list(&revs
,
701 quiet
? finish_commit
: show_commit
,
702 quiet
? finish_object
: show_object
);